ВсОШ 2023, 11 класс, задача 5
( баллов) Юра и Яша играют в следующую игру, делая ходы по очереди. Первым ходит Юра.
Изначально на доске написано число . Игрок в свой ход может прибавить к числу на доске любой его натуральный делитель, стереть старое число и записать новое. (Например, если на доске написано число , то можно его стереть и написать одно из чисел , , , , , .)
Рассмотрим все возможные натуральные значения от до включительно.
(а) ( балла) Для скольких из них Юра имеет выигрышную стратегию, если проигрывает тот, кто получит после своего хода число, не меньшее ?
(б) ( балла) Для скольких из них Юра имеет выигрышную стратегию, если побеждает тот, кто получит после своего хода число, не меньшее ?
Ответ
Ответ: (а) ; (б) .
Решение. (а) Докажем, что игрок, начинающий с чётного числа, выигрывает, а игрок, начинающий с нечётного числа, проигрывает. Действительно, игрок, которому пришло чётное число, может прибавлять к нему (т. к. единица является делителем всех натуральных чисел) и получать нечётное число. Его соперник вынужден прибавлять к нему какое-то нечётное число и получать чётное число. Таким образом, игрок начинающий с чётного числа, выигрывает, т. к. ему каждый ход приходит чётное число, к которому он прибавляет (а из чётного числа, меньшего , таким образом нельзя получить число, не меньшее ). Соответственно, игрок, начинающий с нечётного числа, проигрывает. Таким образом, Юра выигрывает, если — любое чётное число от до , коих штук.
(б) Заметим, что если игроку пришло число, большее , то он может прибавить к нему его же и получить число, не меньшее . Поэтому если начальное число не меньше , то выигрывает Юра. Таких чисел .
Если же начальное число меньше , то игра превращается в игру из пункта (а), только теперь проигрывает игрок, который на своём ходу получает число, которое не меньше . Рассуждая аналогично, можно понять, что Юра выигрывает, только если начальное число чётное. Таких чисел от до ровно . Итого получаем, что Юра выигрывает при значениях .
Верное решение пункта (а).
Верное решение пункта (б).