Задание 19
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается, когда количество камней в куче становится не менее 129. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 129 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 128.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Теория
Данное задание на теорию игр, когда нужно просчитать возможные стратегии хода игры и определить исходное значение (как правило количество камней). Задание решается аналитическим методом довольно быстро. Продолжением этого задания являются задания 20 и 21. Проанализируйте возможные варианты ходов и посчитайте все позиции после хода Пети (Первый игрок) и после хода Вани (Второй игрок). Данный вид задач ранее предполагал изображение на бланке ЕГЭ полного дерева игры, сейчас только ответ. Решение с помощью программы заданий 19 и 20 - трата времени.
Решение
Обозначим начальное значение камней в куче S. За один ход игрок может увеличить количество камней в куче в два раза, или добавить в кучу один камень. Обозначим ходы как S+1 и S*2. Тогда, очевидно, что Петя выигрывает своим первым ходом при 65 ≤ S ≤ 128 - самый быстрый способ увеличения S это S*2. Значит при S<65 Петя первым ходом не выигрывает. Получаем значение S = 64. Поверяем все два возможных хода Пети: 64+1=65, 64*2=128. При любом из этих ходов Ваня выиграет своим первым ходом (увеличив S в два раза или для S=128 прибавив 1).
Для любителей программировать:
При каких S Петя выигрывает первым ходом?
def move(S, t):
if (S+1>=129 or S*2>=129) and t==1:
return True
for S in range(128, 0, -1):
if move(S, 1):
print(S)
Здесь move - функция проверки количества камней в куче S после после хода t=1 - первый ход Пети. Результаты от 128 до 65. Аналогично при каких S Ваня выигрывает своим ответным первым ходом (t=2)?
def move19(S, t):
if (S+1>=129 or S*2>=129) and t==2:
return True
if (S+1<129 and S*2<129) and t==1:
return move19(S+1,t+1) and move19(S*2,t+1)
for S in range(128, 0, -1):
if move19(S, 1):
print(S)
Ответ
64 (Время не более 2 минут)