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

Опишем начальную позицию в виде упорядоченной пары чисел. Например, пара (6, 14) соответствует положению, при котором в меньшей куче 6 камней, а в большей — 14. В этом случае первый игрок может взять из большей кучи 6 или 12 камней.

Выигрышной называется позиция, которая позволяет первому игроку выиграть при верном выборе стратегии. Остальные позиции называются проигрышными. Например, позиции (1,5), (2,6) и (3,12) — выигрышные, поскольку первый игрок может первым же ходом забрать все камни из второй кучи.

Позиции (2,3) и (3,4) — проигрышные, поскольку при любом ходе первого игрока второй участник получает выигрышную позицию.

Обозначим через Z(N) сумму (y_i-x_i) для всех проигрышных позиций (x_i,y_i), 0 < x_i< y_i ≤ N. Можно проверить, что Z(10) = 27 и Z(10⁴) = 24319983959.

Найдите остаток от деления Z(10¹⁶) на 7¹⁰.

Рассмотрим пару последовательностей a_n и s n , заданных следующим образом:

a₁ = 1, s₁ = 1, a_n = s_n-1 mod n, s_n = s_n-1+ a_n×n.

(Здесь и далее "x mod y" означает остаток от деления x на y.)

Первые 10 элементов последовательности an:

1,1,0,3,0,3,5,4,1,9.

Первые 10 элементов последовательности sn:

1,3,3,15,15,33,68,100,109,199.

Обозначим через h(N,M) количество таких пар (p,q), для которых

1≤p≤q≤N  и  (s_p + s_p+1 +… + s_q-1 + s_q ) mod M = 0

Можно проверить, что h(10,10)=5, а соответствующие пары – (1,6), (4,5), (4,9), (6,9) и (8,8).

h(10⁴,10³)= 107796.

Найдите h(10¹²,10⁶).

Широко известна игра, где один из участников задумывает целое число, а другой пытается его угадать, задавая вопросы. В этой задаче исследуется вариант такой игры, когда задумывают натуральное число из промежутка [1,n], а в качестве вопросов разрешается называть натуральные числа из этого же интервала. При этом стоимость каждого вопроса равна названному числу. Допускаются ответы трех видов:

1. Ты назвал число меньше задуманного.
2. Ты угадал!
3. Ты назвал число больше задуманного.

Требуется определить  задуманное число и при этом минимизировать суммарную стоимость вопросов (в дальнейшем – цена игры). Для данного числа n назовем стратегию оптимальной, если она минимизирует цену игры для самого неудачного задуманного числа.

Например, при n=3 наилучшим первым ходом будет число "2". После этого при любом ответе можно будет точно определить задуманное число, поэтому больше вопросов не потребуется, и цена игры будет равна 2.

Если n=8, мы могли бы выбрать в качестве стратегии "бинарный поиск". Если первым ходом мы назовем число "4", а задуманное число будет больше, чем 4, нам потребуется еще два вопроса. Пусть вторым ходом мы называем число "6". Если задуманное число больше, чем 6, нам потребуется еще один ход, скажем, "7", и цена игры составит 4+6+7=17.

Мы можем существенно улучшить нашу стратегию для n=8, если первым ходом назовем число "5". Если задуманное число больше, чем 5, то вторым ходом мы можем назвать число "7", и этого будет достаточно для нахождения задуманного. Тогда цена игры составит 5+7=12. Если же задуманное число меньше, чем 5, то для его определения достаточно  вторым и третьим ходом назвать "3" и "1", а цена игры составит 5+3+1=9. Поскольку 12 > 9, в худшем случае цена игры при этой стратегии будет равна 12. Получается, что данная стратегия более выгодна, чем предыдущая, и оказывается, что она оптимальна, то есть никакая другая стратегия не может гарантировать для n=8 результат меньший, чем 12.

Пусть C(n) – максимальная цена игры, которая может получиться для оптимальной стратегии в худшем случае. 

Тогда C(1) = 0, C(2) = 1, C(3) = 2 и C(8) = 12.

Можно подсчитать, что  C(100) = 400.

Найдите С(500000).

Круглое болото разбито на секторы, перенумерованные по часовой стрелке числами от 1 до 500. Лягушка, сидящая в одном из секторов, может прыгнуть в один из двух соседних секторов с равной вероятностью.

Перед тем, как прыгнуть, лягушка квакает. 

Если номер сектора, в котором сидит лягушка, является простым числом, она с вероятностью 2/3 квакает "P" и с вероятностью 1/3 квакает "N".

Если номер сектора, в котором сидит лягушка, не является простым числом, она с вероятностью 2/3 квакает "N" и с вероятностью 1/3 квакает "P".

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

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

Бесконечная последовательность a(n) определена для всех целых n следующим образом: 

Легко видеть, что

,

,

,

где e = 2,7182818... – основание натурального логарифма. 

Общий член последовательности a(n) можно записать в виде

с натуральными коэффициентами A(n) и B(n).

Например, 

Найдите остаток от деления A(10⁹) + B(10⁹) на 77 777 777. 

На каждую клетку доски N×N положили по шашке, окрашенной в белый цвет с одной стороны и в черный цвет с другой.

Каждым ходом разрешается перевернуть одну шашку, а вместе с нею N-1 шашек, стоящих  на одной с ней вертикали, и N-1 шашек, стоящих  на одной с ней горизонтали. Таким образом, каждым ходом игрок должен перевернуть 2×N-1 шашку. Игра заканчивается, когда все шашки будут стоять белой стороной вверх. Ниже приведен пример игры для доски 5×5.

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

Пусть строки и столбцы перенумерованы целыми числами от 0 до N-1.

Построим на доске N×N начальную конфигурацию C_N. Для этого на клетку с координатами x и y положим шашку черной стороной вверх, если (N-1)²≤x²+y²<N², и белой стороной вверх в противном случае. Конфигурацию C₅ мы видели в приведенном примере.

Пусть T(N) – минимальное количество ходов, необходимых для окончания игры из начального положения C_N (если это невозможно T(N) = 0).

Ясно , что T(1)=T(2)=1. Мы видели, что T(5)=3. Можно проверить, что T(10)=29, а T(1000)=395253.

Найдите сумму T(k!) для 1≤k≤12.

Сферическим треугольником называют фигуру на поверхности сферы, ограниченную дугами больших кругов, имеющими попарно общие концы.

Пусть C(r) – сфера с центром в начале координат (0,0,0) и радиусом r.

Пусть Z(r) – множество точек сферы C(r) с целыми координатами.

Пусть T(r) – множество сферических треугольников с вершинами, принадлежащими Z(r). Вырожденные сферические треугольники с вершинами, принадлежащими одному большому кругу, не включаются в T(r).

Пусть A(r) – наименьшая площадь треугольника из T(r), а B(r) =(4πr²)/A(r) – величина, обратная доле площади сферы, которую занимает наименьший сферический треугольник.

Например, A(14) ≈3,294040, а B(14) ≈ 748.

Найдите максимальное значение B(r) для натуральных r, не превышающих 50. Результат округлите до ближайшего целого.

Любое натуральное число может быть разбито на слагаемые вида 2ⁱ×3^j, где i,j ≥0, но в этой задаче мы будем рассматривать лишь те разбиения, у которых ни одно слагаемое не кратно другому. В дальнейшем будем называть такие разбиения специальными.

Например, разбиение числа 17 = 2 + 6 + 9 = (2¹×3⁰ + 2¹×3¹ + 2⁰×3²) не будет специальным, поскольку 6 кратно 2. Разбиение 17 = 16 + 1 = (2⁴×3⁰ + 2⁰×3⁰) тоже не специальное, так как 16 кратно 1. У числа 17 есть только одно специальное разбиение, а именно 8 + 9 = (2³×3⁰ + 2⁰×3²).

Некоторые числа имеют несколько специальных разбиений. Например, число 11 имеет два специальных разбиения:

11 = 2 + 9 = (2¹×3⁰ + 2⁰×3²) 

11 = 8 + 3 = (2³×3⁰ + 2⁰×3¹)

Обозначим через P(n) количество специальных разбиений числа n. Так, P(11) = 2.

Можно подсчитать, что сумма простых чисел q<100, для которых P(q)=2 равна 641.

Найдите сумму простых q < 1000000, для которых P(q)=2.

Вообразите бесконечный в оба конца ряд чаш, перенумерованных целыми числами.

В некоторых чашах лежат бобы. Разрешается делать ходы следующего вида: взять два боба из одной чаши и разложить их в две соседние. Игра заканчивается, когда сделать ход невозможно.

В примере на рисунке в две соседние чаши положили 2 и 3 боба, а остальные чаши оставили пустыми. Как видно, такую игру можно закончить за 8 ходов.

Рассмотрим последовательность целых чисел bi следующего вида:

b0 = 0, b1 = 289, b2 = 145

bi = (bi-1 + bi-2 + bi-3) mod 2013,

где x mod y означает остаток от деления x на у.

Пусть количество бобов в двух соседних чашах определяется числами b1 = 289 и b2 = 145, а остальные чаши в начальном положении пусты. В этом случае игру можно закончить за 3419100 ходов.

Подсчитайте, сколько ходов потребуется для завершения игры , если в начальном положении в чашах с номерами от 1 до 1500 лежит b1, b2, ... b1500 бобов, соответственно, а остальные чаши пусты.

Несколько чашек расставлены по кругу, и в каждой из них лежит одна горошина. Игрок совершает ходы следующим образом. Он берет все горошины из одной чашки и раскладывает их одну за другой в чашки, следующие за ней по часовой стрелке. При каждом следующем ходе горошины берут из той чашки, куда была положена последняя горошина на предыдущем ходе. Игра заканчивается, когда возвращается к исходному положению, т. е. в с каждой чашке снова оказывается по одной горошине. Вот игра для случая пяти чашек:

Как видно, для пяти чашек игра заканчивается за 15 ходов.

Обозначим через M(x) количество ходов в игре с  x  чашками. Тогда M(5) = 15. Можно проверить, что M(100) = 10920.

Найдите остаток от деления  на 7⁹.