Задание 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: убрать из кучи два камня или убрать из кучи пять камней или уменьшить количество камней в куче в три раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 20 камней за один ход можно получить кучу из 18, 15 или 6 камней.
Игра завершается, когда количество камней в куче становится не более 19. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 19 или меньше камней. В начальный момент в куче было S камней, S ≥ 20.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Теория

Данное задание на теорию игр, когда нужно просчитать возможные стратегии хода игры и определить исходное значение (как правило количество камней). Задание решается аналитическим методом довольно быстро. Продолжением этого задания являются задания 20 и 21. Проанализируйте возможные варианты ходов и посчитайте все позиции после хода Пети (Первый игрок) и после хода Вани (Второй игрок). Данный вид задач ранее предполагал изображение на бланке ЕГЭ полного дерева игры, сейчас только ответ. Решение с помощью программы заданий 19 и 20 - трата времени.

Решение

Обозначим начальное значение камней в куче S. За один ход игрок может: убрать из кучи два камня или убрать из кучи пять камней или уменьшить количество камней в куче в три раза (количество камней, полученное при делении, округляется до меньшего). Обозначим ходы как S-2, S-5 и S//3 (целая часть от деления на 3). Тогда, очевидно, что Петя выигрывает своим первым ходом при 20 ≤ S ≤ 59 - самый быстрый способ уменьшения S - S//3. Значит при S≥60 Петя первым ходом не выигрывает. Получаем минимальное значение S = 60. Поверяем все три возможных хода Пети: 60-2=58, 60-5=55 и 60//3==20. При любом из этих ходов Ваня выиграет своим первым ходом.

Ответ

60 (Время не более 2 минут)