На каждую клетку доски 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.

Любое натуральное число может быть разбито на слагаемые вида 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⁹.

Будем вырезать из бумаги в клетку прямоугольники размером w × h клеток, где w и h – натуральные числа. Некоторые из них можно разрезать по клеточкам на две части так, что из этих частей составится новый прямоугольник другого размера.
Например, прямоугольник размером 9 × 4 клетки можно превратить в прямоугольники 18 × 2, 12 × 3 или 6 × 6, как показано на рисунке:

Аналогично, из прямоугольника 9 × 8 можно сделать прямоугольники размером 18 × 4 и 12 × 6 клеток.
Обозначим через F(w, h) количество различных прямоугольников, которые можно получить из прямоугольника размером w × h клеток. При этом прямоугольники с размерами a × b и b × a считаются одинаковыми, а прямоугольники, конгруэнтные исходному, не учитываются.
Тогда получим: F(2,1) = 0, F(2,2) = 1, F(9,4) = 3 и F(9,8) = 2.
Пусть G(N)=Σ F(w, h) для всех 0 < h ≤ w ≤ N.
Можно проверить, что G(10) = 55, G(10³) = 971745, а G(10⁵) = 9992617687.
Найдите ΣG(10^k), где 1≤k≤12. В качестве ответа укажите 8 младших цифр результата.

Последовательность Голомба {G(n)}  определяют как единственную неубывающую последовательность натуральных чисел, содержащую ровно G(n)  вхождений каждого натурального числа n.
Вот несколько первых значений G(n):

Можно подсчитать, что G(2¹⁰) = 87, G(2²⁰) = 6320, и что ΣG(2ⁿ) = 857297 при 1 ≤ n < 30.

Найдите ΣG(2ⁿ)для 1 ≤ n < 60.

Рассмотрим нечетное число 225 = 3² × 5².
225² = 50625 = 3⁴ × 5⁴ = 9² × 25². Поэтому функция Эйлера φ(50625) = 2 × 3³ × 4 × 5³ = 2³ × 3³ × 5³ .
Итак, число  50625 является квадратом, а φ(50625) является кубом.
Найдите сумму нечетных n, 1 < n < 10¹⁰ , для которых функция Эйлера φ(n²) является кубом натурального числа.

Полем игры из этой задачи является полоска из n клеток, а фишками — монеты.
Одна из этих монет — серебряный доллар — ценная, а остальные — медные — ценности не представляют. Игроки могут совершать ходы двух типов:
1. Сдвинуть любую монету влево на одну или несколько клеток. При этом поставить монету можно только на свободную клетку, и перескакивать через занятые клетки нельзя.
2. Забрать с доски монету, ближайшую к левому краю.
Если ходов первого типа нет, игрок обязан забрать самую левую монету.
Выигрывает тот, кто заберет серебряный доллар.

Выигрышной называется позиция, при которой очередной игрок, правильно выбирая ходы, может обеспечить себе победу независимо от действий второго игрока. Остальные позиции называются проигрышными.
Пусть L(n,c) – количество проигрышных позиций для поля из n клеток, на которое расставляют c медных монет и один серебряный доллар.
Можно проверить, что L(10,3)=150 и L(103,13)= 32792060838490304.
Найдите остаток от деления L(1000003,103) на 1000003.