Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в большую кучу любое количество камней от одного до трёх или удвоить количество камней в меньшей куче. Если кучи содержат равное количество камней, можно добавить в любую из них от одного до трёх камней, удвоение в этой ситуации запрещено.
Игра завершается, когда общее количество камней в кучах становится
Известно, что Петя смог выиграть первым ходом. Какое наименьшее число камней могло быть суммарно в двух кучах?
Приведём решение на языке Python.
def f(x, y, h):
if h == 1 and x + y >= 41:
return 1
if h == 1 and x + y < 41:
return 0
if h < 1 and x + y >= 41:
return 0
else:
if h % 2 == 0:
if x > y:
return f(x + 1, y, h + 1) or f(x + 2, y, h + 1) or f(x + 3, y, h + 1) or f(x, y * 2, h + 1)
elif x < y:
return f(x, y + 1, h + 1) or f(x, y + 2, h + 1) or f(x, y + 3, h + 1) or f(x * 2, y, h + 1)
elif x == y:
return f(x + 1, y, h + 1) or f(x + 2, y, h + 1) or f(x + 3, y, h + 1) or f(x, y + 1, h + 1) or f(x, y + 2, h + 1) or f(x, y + 3, h + 1)
else:
if x > y:
return f(x + 1, y, h + 1) or f(x + 2, y, h + 1) or f(x + 3, y, h + 1) or f(x, y * 2, h + 1)
elif x < y:
return f(x, y + 1, h + 1) or f(x, y + 2, h + 1) or f(x, y + 3, h + 1) or f(x * 2, y, h + 1)
elif x == y:
return f(x + 1, y, h + 1) or f(x + 2, y, h + 1) or f(x + 3, y, h + 1) or f(x, y + 1, h + 1) or f(x, y + 2, h + 1) or f(x, y + 3, h + 1)
a = set()
for x in range(1, 20):
for y in range(1, 20):
if f(x, y, 0) == 1:
a.add(x + y)
print(min(a))
Ответ: 28.
Приведём решение Маргариты Фалько на языке Python.
def g(s1, s2, p, end):
if s1+s2 > 40: return p in end
if p > max(end): return False
moves = []
if s1 > s2:
moves = [g(s1+i, s2, p+1, end) for i in range(1,4)] + [g(s1, s2*2, p+1, end)]
if s1 < s2:
moves = [g(s1, s2+i, p+1, end) for i in range(1,4)] + [g(s1*2, s2, p+1, end)]
if s1 == s2:
moves = [g(s1, s2+i, p+1, end) for i in range(1,4)] + [g(s1+i, s2, p+1, end) for i in range(1,4)]
return any(moves) if ((p+1) % 2) == (end[0] % 2) else all(moves)
print('Задание 19:', min([s1+s2 for s1 in range(1, 100) for s2 in range(1, 100) if g(s1, s2, 0, [1])]))
print('Задание 20:', [s2 for s2 in range(1, 36) if g(5, s2, 0, [3])])
print('Задание 21:', [s2 for s2 in range(1, 24) if g(17, s2, 0, [2, 4]) and not g(17, s2, 0, [2])])
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в большую кучу любое количество камней от одного до трёх или удвоить количество камней в меньшей куче. Если кучи содержат равное количество камней, можно добавить в любую из них от одного до трёх камней, удвоение в этой ситуации запрещено.
Игра завершается, когда общее количество камней в кучах становится
В начальный момент в первой куче было
Укажите минимальное и максимальное из таких
В ответе запишите сначала минимальное значение, затем максимальное.
Ответ:
В игре, описанной
Найдите такое значение S, при котором у Вани есть стратегия, позволяющая ему выиграть вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.