Двое играют в следующую игру. Дано число 0. Разрешается прибавить к текущему числу любое натуральное число от 1 до 9. Выигрывает тот, кто получит число N. Кто выигрывает при правильной игре?

Тот, кто ходит вторым, всегда может увеличить имеющееся число на 10, вне зависимости от того, какое чисто прибавит первый игрок. Если до нужного числа N остается 10, То проигрывает тот, чей сейчас ход. Тактика состоит в том, что первый игрок делает так, чтобы до числа N оставалось число кратное 10, затем постоянно превращает ход соперника в десятку. Например: N = 33. Первый игрок прибавляет 3. Остается 30. Затем, если второй прибавит 2, он прибавит 8, если второй прибавит 6, он прибавит 4 и т. д. чтобы в сумме получилось 10. В этом случае он гарантированно выиграет. Однако, если число N изначально кратно 10, то используя ту же самую тактику, гарантированно побеждает игрок номер 2.

Ответ: Если N кратно 10, то выиграет игрок, который ходит вторым. В остальных случаях выигрывает тот, кто ходит первым.

Назовем число n выигрышным, если у первого игрока есть стратегия, позволяющая получить его первым (с помощью заданных операций) и проигрышным, если такой стратегии нет (то есть, выиграет второй игрок).

Если n = 1, ..., 9, то первый игрок выиграет, а если n = 10, то проиграет, поскольку любой его ход переводит число 0 в число от 1 до 9, то есть, второй следующим ходом победит. На самом деле можно считать, что если первый прибавил, к примеру, 3, то мы перешли к игре, где начинают с нуля и нужно набрать N-3. Поэтому позиция 10 проигрышная, т. к. любой ход - прибавление к нулю 1, 2, ..., 9 приводит нас к игре, где нужно получить 9, 8, ..., 1, то есть в выигрышную для второго ситуацию.

Позиции 11, 12, ..., 19 - тоже выигрышные (мы можем свести ситуацию к игре, где надо набрать 10). Позиция 20 - проигрышная (мы можем попасть только в выигрышную позицию). Продолжая аналогичные рассуждения получим, что позиции, кратные 10, проигрышные (для первого), а все остальные - выигрышные.