|
|
 |
Условие
Лежит кучка в 10 миллионов спичек. Двое играют в следующую игру. Ходят по очереди. За один ход играющий может взять из кучки спички в количестве pn, где p – простое число, n = 0, 1, 2, 3, ... (например, первый берёт 25 спичек, второй – 8, первый – 1, второй – 5, первый – 49 и т.д.). Выигрывает тот, кто берёт последнюю спичку. Кто выиграет при правильной игре?
Решение
Докажем, что если число спичек не кратно 6 (в частности, таково, как в условии), то первый выигрывает.
Поскольку 1, 2, 3, 4, 5 являются степенями простых, то в случае числа спичек равного 6k + r, где 1 ≤ r ≤ 5, первый играющий может добиться того, чтобы после его хода осталось 6k спичек.
Теперь заметим, что степень простого числа не делится на 6, поэтому после следующего хода оставшееся число не кратно 6, в том числе не может стать нулевым.
Значит, первый игрок каждым своим ходом может оставлять число спичек, кратное 6. Таким образом, второй игрок выиграть никогда не сможет, следовательно, выиграет первый.
Ответ
Первый игрок.
