ЕГЭ №20: выигрыш вторым ходом в игре с камнями

Автор: wilgelmzwer , 24 мая 2026
← К списку задач
ege_20_game_one_pile_58_01
Условие задачи

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза.

Например, если в куче было 10 камней, за один ход можно получить 11 или 20 камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 58. Победителем считается игрок, сделавший последний ход.

В начальный момент в куче было S камней, где 1 ≤ S ≤ 57.

Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

В ответе запишите найденные значения в порядке возрастания через пробел.

Проверка ответа

.
Подсказка

Сначала найдите позицию, из которой любой ход приводит к немедленному выигрышу следующего игрока. Затем найдите такие начальные S, из которых Петя может одним ходом перевести игру в эту позицию.

Решение

Сначала найдём позиции, из которых игрок может выиграть за один ход. Для этого должно выполняться одно из условий:

S + 1 >= 58 или 2 * S >= 58

Значит, игрок выигрывает за один ход при S ≥ 29.

Теперь найдём позицию, из которой любой ход ведёт в область S ≥ 29. Это позиция S = 28:

28 + 1 = 29
28 * 2 = 56

После любого хода из 28 следующий игрок сможет выиграть за один ход. Значит, Петя хочет своим первым ходом получить 28 камней.

Получить 28 можно двумя способами:

S + 1 = 28  =>  S = 27
2 * S = 28  =>  S = 14

Оба значения меньше 29, значит Петя не выигрывает первым ходом. Подходящие значения: 14 и 27.

Ответ: 14 27.

Входит в комплекты

Эта задача используется в подборках, связках или тренировочных наборах.

ЕГЭ
Задание 20
ЕГЭ №20
Теория игр
Динамическое программирование
Рекурсия
4 - сложная
Авторская задача