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

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

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

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

Вагоны поезда обозначены буквами латинского алфавита: A,B,C,D..., и последовательность вагонов в железнодорожном составе можно задать с помощью соответствующей цепочки букв.

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

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

В некоторых случаях сформировать состав совсем просто. Например, когда исходный порядок вагонов ADCB, вагоны можно расцепить между A и D, затем развернуть фрагмент DCB, и, наконец, сцепить вагоны в нужном порядке. Результат достигается всего за один шаг, т.е. за один поворот круга на 180 градусов.

Возможно, процесс можно оптимизировать, но машинист пользуется совсем простым алгоритмом. Сначала он стремиться прицепить вагон A следом за паровозом, затем следом за ним вагон B, и так далее.

Машинист выяснил, что для состава из четырех вагонов потребуется не более 5 шагов. Максимальное количество - 5 операций - требуется для двух начальных последовательностей, а именно DACB и DBAC. Последовательности вагонов, требующие наибольшего количества операций для упорядочения, будем называть пессимальными.

Порядок формирования состава для начальной последовательности  DACB показан на рисунке.

Для состава из шести вагонов машинист составил список пессимальных последовательностей. Список содержал 24 последовательности. Последовательности он расположил в алфавитном порядке, и цепочка DFAECB оказалась на десятом месте от начала.

Представьте, что вам поручили составить список пессимальных последовательностей для составов из 11 вагонов и упорядочить получившийся список в алфавитном порядке.

На каком месте в списке окажется последовательность CIAKBGHFJDE?

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

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

Космонавты осваивают планету, имеющую радиус r. Они построили две станции на полюсах планеты, имеющих координаты (0,0,r) и (0,0,-r) в системе координат, связанной с центром планеты.
Также они установили несколько промежуточных станций, расположенных во всех точках поверхности планеты, имеющих целые координаты.

Все станции связаны дорогами, проложенными по кратчайшей дуге большого круга, однако путь между станциями требует больших затрат, равных (d/(π r))², где d – протяженность дороги между двумя станциями. Если маршрут включает посещение нескольких промежуточных станций, затраты на все путешествие равны сумме затрат на отдельных участках.
Маршрут, проложенный между полюсами планеты и не проходящий через промежуточные станции, будет иметь длину πr, а затраты будут равны 1. Если же включить в маршрут одну промежуточную станцию с координатами (0,r,0), затраты уменьшатся вдвое:   (½πr/(πr))²+(½πr/(πr))²=0,5.
Будем называть оптимальным маршрут между полюсами планеты, если он требует минимальных затрат.
Например, при r=7 оптимальный маршрут будет проходить через 6 промежуточных станций, а затраты составят примерно 0,1784943998…
Подсчитайте, сколько промежуточных станций посетят космонавты, путешествуя по оптимальному маршруту между полюсами планеты с r=33333.

Циклическим называют натуральное число из n знаков, обладающее следующим интересным свойством: если умножить его на 1, 2, 3, 4,…, n-1 или n, то произведение будет состоять из тех же цифр, но переставленных циклически.

Если не считать тривиального числа 1, наименьшим циклическим числом будет 142857:
142857 × 1 = 142857
142857 × 2 = 285714
142857 × 3 = 428571
142857 × 4 = 571428
142857 × 5 = 714285
142857 × 6 = 857142

Если, как это обычно принято, не писать нулей в старших разрядах, то больше циклических чисел мы не обнаружим. Однако если начинать с нулей, можно найти их бесконечно много, например, следующим циклическим будет 16-значное число 0588235294117647:

0588235294117647 × 1 = 0588235294117647
0588235294117647 × 2 = 1176470588235294
0588235294117647 × 3 = 1764705882352941
...
0588235294117647 × 16 = 9411764705882352

Найдите наибольшее циклическое число, которое начинается цифрами 00000000123 и заканчивается цифрами 56789 (то есть число вида 00000000123...56789, где многоточие означает некоторое неизвестное количество цифр). В качестве ответа укажите сумму его цифр.

В отеле "Инфинити" бесконечно много этажей, на каждом этаже бесконечно много комнат, а к администратору выстроилась бесконечно длинная очередь. И этажи, и комнаты на каждом этаже, и посетители перенумерованы подряд натуральными числами (1, 2, 3, …).
В начальный момент все комнаты отеля свободны. Чтобы поселить очередного гостя с номером n,  администратор выбирает самый нижний этаж, на котором либо пока никто не живет, либо последний поселившийся имеет такой номер m, что m+n является квадратом целого числа. Новый гость получает первый свободный номер на выбранном этаже.
 Гость №1 получает комнату №1 на первом этаже, поскольку на нем еще никто не живет.
 Гостя №2 нельзя поселить в комнате №2 на первом этаже, поскольку сумма 1+2=3 не является квадратом. Этого гостя можно поселить на втором, пока еще пустом этаже, в комнате №1.
 Гость №3 получает комнату №2 на первом этаже, поскольку сумма 1+3=4 является квадратом.
Таким образом, каждый гость получит свою комнату в отеле.
Обозначим через P(f, r) номер посетителя, живущего в комнате r на этаже f.
Тогда:
P(1, 1) = 1
P(1, 2) = 3
P(2, 1) = 2
P(10, 20) = 440
P(25, 75) = 4863
P(99, 100) = 19454
Найдите сумму P(f, r) для всех f и r, таких что f² + r² = 14234886498625 .