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

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

В примере на рисунке в две соседние чаши положили 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 младших цифр результата.

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

Первоначально каждое стадо состоит из n овец. Каждая овца, независимо от масти, может заблеять в очередной раз. Передур стремится максимизировать количество черных овец. Для этого он может прогонять прочь любое количество белых овец, но делать это он может лишь после того, как заблеяла очередная овца и до того, как овца с противоположного берега вошла в реку.
Пусть E(n) – ожидаемое количество черных овец, которое останется у Передура при оптимальной стратегии. Например, E(5) ≈ 6.871346…
Найдите наименьшее n, для которого E(n)>20000.

Пусть  a, b, c – натуральные числа, а функция F(n) определена следующим образом:
F(n) = n - c при n > b
F(n) = F(a + F(a + F(a + F(a + n)))) при n ≤ b. 
Пусть также 

Тогда, например, при a = 50, b = 2000 и c = 40, получим F(0) = 3240, F(2000) = 2040,
а Z(50, 2000, 40) = 5044935.
Найдите остаток от деления Z(21⁷, 7²¹, 12⁷) на 987654321.

Рассмотрим нечетное число 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.

В этой задаче мы будем рассматривать натуральные числа, имеющие ровно три простых делителя. Например, число 240 имеет простые делители 2,3 и 5. Это наибольшее число, не превышающее 250, имеющее эти три простых делителя и не имеющее других.

Для различных простых чисел p, q и r обозначим через M(p,q,r,N) наибольшее натуральное число, не превышающее N, которое делится на p, q и r, но не имеет других простых делителей. Если таких чисел нет, будем считать, что M(p,q,r,N)=0.

Например:

• M(2,3,5,250)=240.
• M(2,3,7,250)=168, а не 210, поскольку число 210 имеет 4 простых делителя.
• M(3,7,13,250)=0, поскольку нет натуральных чисел, не превышающих 250, которые делятся на 3, 7 и 13.

Пусть S(N) – сумма различных значений M(p,q,r,N) для всех сочетаний p, q и r. Так, S(250)= 4588.

Найдите  S(10 000 000).

Степени двойки, как известно, редко начинаются с цифры 9 (см. задачу 316). Так, первый раз это случается только для 53-й степени (2⁵³ = 9007199254740992). С двух девяток подряд начинается 93-я степень, а с трех девяток - только 2621-я.

Найдите минимальный показатель степени n такой, что десятичная запись числа 2ⁿ начинается с десяти девяток подряд.