Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. Изменять количество камней в большей куче не разрешается. Пусть, например, в начале игры в первой куче
Игра завершается, когда общее количество камней в двух кучах становится
В начальный момент в первой куче было
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное и максимальное из таких
В ответе запишите сначала минимальное значение, затем максимальное.
Ответ:
Рассмотрим значение S = 31. Своим первым ходом Петя может получить позиции (13, 31), (14, 31) и (24, 31). К победе Петю приводит позиция (24, 31). Сколько бы камней не добавил Ваня, он не сможет получить более 80 камней суммарно, и Петя выигрывает на своем втором ходе. При остальных позициях Петя не сможет выиграть у Вани своим вторым ходом.
Второе значение S — 54. Своим первым ходом Петя может получить позиции (13, 54), (14, 54) и (24, 54). К победе Петю приводит позиция (13, 54). Сколько бы камней не добавил Ваня, он не сможет получить более
Ответ: 31 54.
Приведем решение Юрия Красильникова на языке 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 == 3 and a+b > 80: return 1
if n == 3 and a+b <= 80: return 0
if n <3 and a+b > 80: return 0
else:
if n%2==0:
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==1:
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)
m=[]
for s in range(1,69):
if F(12,s,0):
m.append(s)
print(min(m),max(m))
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. Изменять количество камней в большей куче не разрешается. Пусть, например, в начале игры в первой куче
Игра завершается, когда общее количество камней в двух кучах становится
В начальный момент в первой куче было
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное из таких
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. Изменять количество камней в большей куче не разрешается. Пусть, например, в начале игры в первой куче
Игра завершается, когда общее количество камней в двух кучах становится
В начальный момент в первой куче было
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найдите максимальное из таких