Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней, не меньше одного камня в каждой. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в большую кучу любое количество камней от одного до трёх или удвоить количество камней в меньшей куче. Если кучи содержат равное количество камней, можно добавить в любую из них от одного до трёх камней, удвоение в этой ситуации запрещено.
Игра завершается в тот момент, когда количество камней в одной из куч
Такая ситуация возможна при S = 46. Могут быть кучи
Приведем решение на языке Python.
from itertools import product as p
def Win(ma, mi, k):
ma, mi = max(ma, mi), min(ma, mi)
return 0 if ma >= 48 or mi >= 48 else any([Lose(ma+i,mi,k-1) for i in range(1,4)] + [Lose(ma,mi*2,k-1)] if ma!=mi\
else [Lose(ma+i,mi,k-1) for i in range(1,4)])
def Lose(ma, mi, k):
ma, mi = max(ma, mi), min(ma, mi)
return 1 if ma >= 48 or mi >= 48 else 0 if not k else\
all([Win(ma+i,mi,k-1) for i in range(1,4)] + [Win(ma,mi*2,k-1)] if ma!=mi else [Win(ma+i,mi,k-1) for i in range(1,4)])
print('Задание 19:', min([x+y for x, y in p(range(1,48), repeat=2) if Win(x, y, 1)]))
Ответ: 46.
Приведем решение Даниила Травинова на языке Python.
def game(p1, p2, mov):
if (p1 >= 48 or p2 >= 48) and mov == 2:
return 1
elif mov > 2:
return 0
else:
if p1 > p2:
return game(p1 + 1, p2, mov + 1) or game(p1 + 2, p2, mov + 1) or game(p1 + 3, p2, mov + 1) or game(p1, p2 * 2, mov + 1)
elif p1 == p2:
return game(p1 + 1, p2, mov + 1) or game(p1 + 2, p2, mov + 1) or game(p1 + 3, p2, mov + 1) or game(p1, p2 + 1, mov + 1) or game(p1, p2 + 2, mov + 1) or game(p1, p2 + 3, mov + 1)
else:
return game(p1, p2 + 1, mov + 1) or game(p1, p2 + 1, mov + 1) or game(p1, p2 + 3, mov + 1) or game(p1 * 2, p2, mov + 1)
sum = float('inf')
for i in range(1, 47):
for j in range(1, 47):
if game(i, j, 1) == 1:
sum = min(sum, i + j)
print(sum)
В игре, описанной
Укажите минимальное и максимальное из таких
В ответе запишите сначала минимальное значение, затем максимальное.
Ответ:
В игре, описанной
Найдите такое значение S, при котором у Вани есть стратегия, позволяющая ему выиграть вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.