Мы хотим приготовить пиццу круглой формы, состоящую из m?n ломтей-секторов одного размера, но с разной начинкой. У нас есть m≥2 сортов начинки, и каждый сорт мы должны использовать ровно для n ломтей.

Обозначим через f(m,n) количество способов приготовления пиццы, в которой будет ровно n ломтей, заправленных начинкой каждого из m сортов. Поскольку пиццу можно крутить как угодно вокруг вертикальной оси, но нельзя переворачивать начинкой вниз, зеркально симметричные варианты считаются различными, а варианты, отличающиеся только поворотом, предполагаются одинаковыми.

Например, f(2,1)=1,  f(2,2)=f(3,1)=2 и  f(3,2)=16.

Случай f(3,2) показан на рисунке:

Найдите сумму всех f(k,k), не превышающих 10¹⁵.

Функция Аккермана  рекурсивно задается для неотрицательных целых чисел  и  следующим образом:

Например, ,  и .

Чему равен остаток от деления  на 14⁸, где ?

Сколько существует 18-значных натуральных чисел n, таких, что сумма цифр n равна сумме цифр числа 137n?

Для натурального числа k обозначим через d(k) сумму его десятичных цифр. Например, d(42) = 4+2 = 6.

Обозначим через S(n) количество натуральных чисел k < 10ⁿ, таких что 

• k делится на 69;
• d(k) = 69. 

Можно подсчитать, что S(9) = 5464, и S(20) = 36035277144875036.

Найдите остаток от деления S(20¹²) на 10⁹.

В сильно  упрощенной модели белки можно рассматривать как цепочки гидрофобных (H) и полярных (P) элементов, например HHPPHHHPHHPH.

В этой задаче мы будем считать, что ориентация белка существенна, то есть белки HPP и PPH мы будем считать различными, а количество белков из n элементов будет равно 2ⁿ.

Гидрофобные элементы притягиваются друг к другу, и белок принимает наиболее энергетически выгодную конфигурацию так, чтобы максимизировать количество связей H-H. 

Поэтому элементы H часто находятся внутри белка, а элементов P больше снаружи. Конечно, настоящие белки имеют трехмерные конфигурации, но мы еще несколько упростим модель, ограничившись двумя измерениями и предполагая, что звенья цепочки занимают места в клетках квадратной решетки.

На рисунке показаны две конфигурации одного белка (связи H-H отмечены красными точками)

В конфигурации слева сформировалось всего лишь 6 связей H-H, поэтому такая конфигурация энергетически невыгодна и не может встретиться в природе.

Правая конфигурация имеет девять связей H-H, и это максимальное значение для такой цепочки. Будем называть оптимальными те конфигурации, которые обеспечивают максимальное количество связей H-H для данной цепочки.

77 из 256 восьмиэлементных цепочек в оптимальной конфигурации имеют более 4 связей H-H.

Сколько цепочек, состоящих из 15 элементов, в оптимальной конфигурации будут иметь более 9 связей H-H?

Ним – это игра, в которой двое участников по очереди берут камни, разложенные на несколько кучек. Каждым ходом игрок должен взять из одной кучки один или несколько камней, но хотя бы один – обязательно!

Проигрывает тот, кому камней не досталось, и кто поэтому не может сделать ход.

Мы рассмотрим наиболее популярную версию игры с тремя кучками камней.

Пусть начальная позиция описывается тройкой чисел (n1,n2,n3), где  n1,n2 и n3 - количество камней в каждой из трех кучек.

• Позиция называется выигрышной, если первый игрок, правильно выбрав стратегию, может гарантировать свою победу.
• Позиция называется проигрышной, если первый игрок при правильной игре второго всегда проигрывает.

Например, позиция (0,n,n) – проигрышная для любых n, ибо второй игрок всегда может выравнивать количество камней в двух оставшихся кучках, пока в них что-то остается. По этой же причине позиция (1,2,3) – тоже проигрышная, ибо второй игрок своим ходом всегда может создать позицию вида (0,n,n), например:

Первый игрок: (1,2,1)         Второй игрок: (1,0,1)

Первый игрок: (0,0,1)         Второй игрок: (0,0,0) – победа.

Подсчитайте, сколько существует проигрышных позиций вида (n,2n,3n), где n – натуральное число, не превышающее 10¹².

Назовем натуральное число n мощным, если для его любого простого делителя p число n делится также на p².

Назовем натуральное число n точной степенью, если оно является степенью другого натурального числа.

Назовем натуральное число n ахиллесовым, если оно мощное, но не является точной степенью. Например, числа 864 = 2⁵•3³ и 1800 = 2³•3²•5² — ахиллесовы.

Назовем натуральное число S сильно ахиллесовым, если и S, и φ(S) — ахиллесовы.  Здесь φ(S) означает функцию Эйлера. 

Например, число 864 — сильно ахиллесово число, поскольку φ(864) = 288 = 2⁵•3², а число 1800 — ахиллесово, но не сильно ахиллесово, так как φ(1800) = 480 = 2⁵•3¹•5¹.

Существует 2 трехзначных и 5 четырехзначных сильно ахиллесовых чисел, а восьмизначных насчитывается 396.

Найдите количество 18-значных сильно ахиллесовых чисел.

Как известно, последовательность Фибоначчи определяется рекуррентно:

f(0)=0 , f(1)=1, и f(n)=f(n-1)+f(n-2) при n>1.

Найдите Σf(p_i), где p_i – простые числа, и 10¹⁴< p_i <10¹⁴+5*10⁶.

Остаток от деления полученной суммы на 1234567891011 будет ответом к этой задаче.

Рассмотрим бесконечную строку S, состоящую из записанных подряд натуральных чисел в десятичной записи:

S =1234567891011121314151617181920212223242...

Ясно, что десятичная запись каждого натурального числа n встретится в строке S бесконечно много раз. Будем отмечать, где именно встретились такие вхождения. Например, число 12 первый раз встретится, начиная с позиции 1 строки S, а второй раз — с позиции 14, и так далее.

Обозначим через f(n) номер позиции в строке S, с которого начинается n-ое вхождение числа n. Например, f(1)=1, f(5)=81, f(11)=235, а f(7780)=111111365.

Найдите ∑f(11^k), где 1≤k≤6.

Рассмотрим игру для двух участников. Игровое поле представляет собой полоску из n клеток белого цвета. Ходы совершают по очереди. Каждым ходом игрок должен закрасить любые две соседние белые клетки. Проигрывает тот, кто не может сделать ход.

• При n=1 первый игрок автоматически проигрывает, поскольку не может сделать ни одного хода.
• При n=2 есть только один ход, который автоматически ведет к победе.
• При n=3 первый игрок может выбрать один из двух различных ходов, и оба они ведут к немедленной победе.
• При n=4 есть три варианта хода. Среди них есть один выигрышный ход, когда игрок закрашивает две средние клетки.
• При n=5 есть четыре варианта хода (они показаны на рисунке красным цветом), но все они ведут к поражению: второй игрок (показан синим цветом) всегда может выиграть.

Таким образом, первые три значения n, при которых первый игрок выигрывает – это 2,3 и 4, а первые два проигрышных значения – это 1 и 5. Третье проигрышное значение n=9, десятое: n=43.

Найдите миллионное значение n, при котором второй игрок всегда может победить.