Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня, либо увеличить количество камней в куче в четыре раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда количество камней в куче становится
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу
В начальный момент в куче было
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное
Такое значение S — 19. Своим первым ходом Петя может получить
Ответ: 19.
Приведём другое решение на языке Python.
Для контроля ходов игроков заведём переменную m.
Если m = 1, то это действие x + 1.
Если m = 2, то это действие x + 4.
Если m = 3, то это действие x · 4.
Таким образом, можно исключать ходы, которые уже были сделаны, не включая их в возвращаемые значения функции.
def f(x, h, m):
if h == 3 and x >= 78:
return 1
elif h == 3 and x < 78:
return 0
elif x >= 78 and h < 3:
return 0
else:
if h % 2 == 0:
if h == 2:
if m == 1:
return f(x + 1, h + 1, m) or f(x * 4, h + 1, m)
elif m == 2:
return f(x + 4, h + 1, m) or f(x * 4, h + 1, m)
elif m == 3:
return f(x + 1, h + 1, m) or f(x + 4, h + 1, m)
else:
return f(x + 1, h + 1, 1) and f(x + 4, h + 1, 2) and f(x * 4, h + 1, 3)
for x in range(1, 78):
if f(x, 1, 0) == 1:
print("Задача 19:", x)
break
Приведём решение Евгения Джобса (аналитическое).
Изобразим игру схематически:
Сперва определим все
Следовательно, при
Чтобы найти выигрышные позиции для игры длиной в два хода (вопрос задачи), необходимо, чтобы после первого хода следующий игрок ходил из выигрышной позиции для игры длиной в один ход.
Приведём решение Евгения Джобса (электронные таблицы, формула).
Вставим
В ячейке В1 запишем формулу для победы первым
=ЕСЛИ(ИЛИ(А1+1>79;A1+4>79;A1*4>79);1;0).
В ячейке C1 запишем формулу для победы вторым ходом:
B1 =ЕСЛИ(ИЛИ(A1+1>79;A1+4>79;A1*4>79);1;0).
Условие B1 = 1 гарантирует, что проверяемое значение не удовлетворяло игре в один ход. ИНДЕКС(В:В;А1*4) возвращает значение
Приведём решение Юрия Красильникова на языке Python.
def move(n,lim,s):
# n - номер хода, lim - ограничение на число ходов, s - число камней
# Результат: 1 - выиграл первый игрок, 2 - второй, 0 - победителя нет
player = 2 - n%2# Текущий игрок
rival = 3 - player# Противник
if s >= 78:# Игра уже окончена
return rival # Выиграл сделавший предыдущий ход
if n > lim:# Превышен лимит ходов
return 0# Победитель не определен
pos = [s+1, s+4, s*4]# Позиции после хода игрока
res = [move(n+1, lim, x) for x in pos]# Результаты ходов
if any([x == player for x in res]):# Есть выигрышный ход
return player
if all([x == rival for x in res]):# Все ходы проигрышные
return rival
return 0# Победитель не определен
print('#19:',*[s for s in range(1,78) if move(1,2,s)==2])
print('#20:',*[s for s in range(1,78) if move(1,1,s)==0 and move(1,3,s)==1])
print('#21:',*[s for s in range(1,78) if move(1,2,s)==0 and move(1,4,s)==2])
Для игры, описанной
Ответ:
Для игры, описанной
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
