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

Условие:

На доске написано число 60. Играют двое, ходят по очереди. За один ход разрешается уменьшить число на один из его натуральных делителей (в том числе на единицу или само это число). Если при этом получается нуль, игрок проиграл. Кто выигрывает при правильной игре?

Решение:

Допустим в некоторой игре невозможны ничьи (например, в этой). Введем некоторые понятия:

Выигрышная позиция -- позиция, попав в которую, игрок выигрывает при правильной игре соперника.

Проигрышная позиция -- позиция, попав в которую, игрок проигрывает при правильной игре соперника.

Нетрудно видеть, что если из позиции можно попасть только в проигрышные позиции, то она выигрышная. Если из позиции можно попасть в выигрышную, то она проигрышная. Позиция "1", например, выигрышная.

Число 59 простое, значит из позиции "59" можно попасть только в позиции "58" и "0". Если позиция "58" проигрышная, то позиция "59" выигрышная. Таким образом, если позиция "58" выигрышная то первый игрок ходит в нее и выигрывает, иначе ходит в позицию "59" и также выигрывает.

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