Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. Изменять количество камней в большей куче не разрешается. Пусть, например, в начале игры в первой куче
Игра завершается, когда общее количество камней в двух кучах становится
В начальный момент в первой куче было
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное из таких
Такая ситуация возможна при S = 55. При этом в одной из куч
Ответ: 55.
Приведем решение Юрия Красильникова на языке Python.
def move(n,lim,s):
# n - номер хода, lim - ограничение на число ходов, s - числа камней в кучах (кортеж)
# Результат: 1 - выиграл первый игрок, 2 - второй, 0 - победителя нет
player = 2 - n%2# Текущий игрок
rival = 3-player# Противник
if sum(s) > 80:# Игра уже окончена
return rival# Выиграл сделавший предыдущий ход
if n > lim:# Превышен лимит ходов
return 0# Победитель не определен
s1,s2 = s# Распаковка позиции
pos = [(s1+1,s2),(s1+2,s2),(s1*2,s2)] if s1 < s2 else [(s1,s2+1),(s1,s2+2),(s1,s2*2)]
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,69) if move(1,2,(12,s)) == 2])
print('#20:',*[s for s in range(1,69) if move(1,1,(12,s)) == 0 and move(1,3,(12,s)) == 1])
print('#21:',*[s for s in range(1,69) if move(1,2,(12,s)) == 0 and move(1,4,(12,s)) == 2])
Приведем решение Михаила Глинского на языке Python.
def F(a,b,n):
if n == 2 and a+b > 80: return 1
if n == 2 and a+b <= 80: return 0
if n == 1 and a+b > 80: return 0
else:
if n%2==1:
if a < b: return F(a+1,b,n+1) or F(a+2,b,n+1) or F(a*2,b,n+1)
else: return F(a,b+1,n+1) or F(a,b+2,n+1) or F(a,b*2,n+1)
if n%2==0:
if a < b: return F(a+1,b,n+1) and F(a+2,b,n+1) and F(a*2,b,n+1)
else: return F(a,b+1,n+1) and F(a,b+2,n+1) and F(a,b*2,n+1)
for s in range(1,69):
if F(12,s,0):
print(s)
break
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. Изменять количество камней в большей куче не разрешается. Пусть, например, в начале игры в первой куче
Игра завершается, когда общее количество камней в двух кучах становится
В начальный момент в первой куче было
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное и максимальное из таких
В ответе запишите сначала минимальное значение, затем максимальное.
Ответ:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. Изменять количество камней в большей куче не разрешается. Пусть, например, в начале игры в первой куче
Игра завершается, когда общее количество камней в двух кучах становится
В начальный момент в первой куче было
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найдите максимальное из таких