Решение задачи 369

Условие:

Лежит кучка в 10 миллионов спичек. Двое играют в следующую игру. Ходят по очереди. За один ход играющий может взять из кучки спички в количестве pⁿ, где p – простое число, n = 0, 1, 2, 3, ... . Выигрывает тот, кто берёт последнюю спичку. Кто выиграет при правильной игре?

Решение:

Заметим, что 1, 2, 3, 4, 5 являются степенями простых, а 6 не является степенью простого. Более того, никакое число, кратное шести, не является степенью простого. Это значит, что если количество спичек кратно шести, то после любого хода, их количество не будет кратно шести.

У первого игрока есть простая тактика: брать столько спичек, чтобы после его хода количество оставшихся спичек было кратно шести. Пусть перед ходом первого игрока лежат 6n+k (1≤k≤5) спичек, тогда своим ходом первый игрок берет k спичек. Как было показано ранее, после очередного хода второго игрока,количество спичек не будет кратно шести. Осталось заметить, что изначально число спичек (10 миллионов) не кратно шести.

Ответ: Первый игрок.