Тип 19 № 56519 
Выигрышная стратегия. Задание 1. Две кучи
i
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу любое количество камней от одного до количества камней в этой куче. Изменять количество камней в большей куче не разрешается. Если кучи содержат равное количество камней, добавлять камни можно в любую из них. Пусть, например, в начале игры в первой куче 3 камня, а во второй — 5 камней, будем обозначать такую позицию (3, 5). Петя первым ходом должен добавить в первую кучу от 1 до 3 камней, он может получить позиции (4, 5), (5, 5) и (6, 5). Если Петя создаёт позицию (4, 5), то Ваня своим ходом может добавить от 1 до 4 камней в первую кучу, а если Петя создаёт позицию (6, 5), то Ваня может добавить от 1 до 5 камней во вторую кучу, так как теперь она стала меньшей. В позиции (5, 5) Ваня может добавить от 1 до 5 камней в любую кучу.
Игра завершается, когда общее количество камней в кучах становится более 45. Победителем считается игрок, сделавший последний ход, то есть первым получивший 46 или больше камней в двух кучах.
Известно, что Петя смог выиграть первым ходом. Какое наименьшее число камней могло быть суммарно в двух кучах?
Решение. Пусть S — сумма камней в обеих кучах. Такая ситуация возможна при S = 31, при этом в одной из куч должно быть 16 камней, а во второй — 15. Добавив ещё 15 камней в меньшую кучу, получается позиция (16, 30), которая в сумме даёт 46 камней, и Петя побеждает. При S < 31 Петя не сможет выиграть первым ходом.
Ответ: 31.
Приведём решение Дмитрия Пехова на языке Python.
def f(a,b,m):
if a+b >= 46:
return m%2==0
if m==0:
return 0
h = []
if a <= b:
for i in range(1,a+1):
h.append(f(a+i,b,m-1))
else:
for i in range(1,b+1):
h.append(f(a,b+i,m-1))
if (m-1)%2==0:
return any(h)
else:
return all(h)
print('19)', min([s1 + s2 for s1 in range(1,46) for s2 in range(1,46) if f(s1,s2,1)]))
print('20)', min([s2 for s2 in range(1,41) if not f(5,s2,1) and f(5,s2,3)]))
print('20)', max([s2 for s2 in range(1,41) if not f(5,s2,1) and f(5,s2,3)]))
print('21)', min([s2 for s2 in range(1,41) if not f(5,s2,2) and f(5,s2,4)]))
Приведём решение Юрия Красильникова на языке Python.
def ход(номер,лимит,позиция):
игрок=2-номер%2
враг=3-игрок
if sum(позиция)>=46: return враг
if номер>лимит: return 0
куча1,куча2=позиция
if куча1<куча2: позиции=[(куча1+добавка,куча2) for добавка in range(1,куча1+1)]
else: позиции=[(куча1,куча2+добавка) for добавка in range(1,куча2+1)]
результаты=[ход(номер+1,лимит,поз) for поз in позиции]
if any(рез==игрок for рез in результаты): return игрок
if all(рез==враг for рез in результаты): return враг
return 0
print('#19:',min([куча1+куча2 for куча1 in range(1,44) for куча2 in range(1,44) if ход(1,1,(куча1,куча2))==1]))
print('#20:',*[куча2 for куча2 in range(1,41) if ход(1,1,(5,куча2))==0 and ход(1,3,(5,куча2))==1])
print('#20:',*[куча2 for куча2 in range(1,41) if ход(1,2,(5,куча2))==0 and ход(1,4,(5,куча2))==2])
Приведём решение Юрия Ворошилова на языке Python.
def f(x,y,n):
if x+y >= 46 and n==1:
return 1
if x+y < 46 and n==1:
return 0
if x+y >= 46 and n%2==0:
return 0
if x+y < 46 and n%2==1:
a=[]
if x < y:
for i in range(1,x+1): a.append(f(x+i, y, n+1))
else:
for i in range(1,y+1): a.append(f(x, y+i, n+1))
return all(a)
if x+y < 46 and n%2==0:
a=[]
if x < y:
for i in range(1,x+1): a.append(f(x+i, y, n+1))
else:
for i in range(1,y+1): a.append(f(x, y+i, n+1))
return any(a)
mn = 46
for x in range(1,46):
for y in range(1,46):
if f(x, y, 0): mn=min(mn, x+y)
print(mn)
Приведём решение Маргариты Фалько на языке Python.
def g(s1, s2, p, end):
if s1 + s2 > 45: return p in end
if p > max(end): return False
moves1 = [g(s1+i, s2, p+1, end) for i in range(1, s1+1) if s1 <= s2]
moves2 = [g(s1, s2+i, p+1, end) for i in range(1, s2+1) if s2 <= s1]
moves = moves1 + moves2
return any(moves) if ((p+1) % 2) == (end[0] % 2) else all(moves)
print('Задание 19:', min([s1+s2 for s1 in range(1,44) for s2 in range(1,44) if g(s1, s2, 0, [1])]))
res_20 = [s1 for s1 in range(1,44) if g(s1, 5, 0, [1, 3]) and not g(s1, 5, 0, [1])]
print('Задание 20:', min(res_20), max(res_20))
print('Задание 21:', min([s1 for s1 in range(1,40) if g(s1, 5, 0, [2, 4]) and not g(s1, 5, 0, [2])]))
PDF-версии: