Решение. Такая ситуация возможна при S = 46. Могут быть кучи (45, 44 и меньше), (46, 45 и меньше), (47, 46 и меньше) и (24, 25 и больше). Поскольку нам необходимо набрать наименьшее количество камней суммарно в двух кучах, то такая позиция (45, 1). Петя увеличит количество камней в большей куче на три и выиграет первым ходом.
Приведем решение на языке 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)
Приведем решение Маргариты Фалько на языке Python.
def g(s1, s2, p, end):
if s1 > 47 or s2 > 47: 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, 48) if g(13, s2, 0, [3]) and not g(13, s2, 0, [1])])
print('Задание 21:', [s2 for s2 in range(1, 48) if g(39, s2, 0, [2, 4]) and not g(39, s2, 0, [2])])
PDF-версии: 