Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. Изменять количество камней в большей куче не разрешается. Пусть, например, в начале игры в первой куче
Игра завершается, когда общее количество камней в двух кучах становится
В начальный момент в первой куче было 8 камней, а во второй —
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найдите максимальное из таких
Такое значение S — 38. При S = 38 Петя своим первым ходом может получить позиции (9, 38), (10, 38) и (16, 38). В позиции (16, 38) Ваня выигрывает первым ходом увеличив количество камней в два раза. Из позиций (9, 38) и (10, 38) Ваня делает
Ответ: 38.
Приведём решение Михаила Глинского на языке Python.
def f(a,b,n):
if (n==2 or n==4) and a+b > 60: return 1
if n==4 and a+b<=60: return 0
if (n==1 or n==3) and a+b > 60: return 0
else:
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)
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)
m=[]
for s in range(1,53):
if f(8,s,0):
m.append(s)
print((m))#Заметим, что если поменять условие победы Вани на только первый ход, то будет 2 числа [ 43, 44]. Они не годятся по условию задачи. Максимальное число - 38
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. Изменять количество камней в большей куче не разрешается. Пусть, например, в начале игры в первой куче
Игра завершается, когда общее количество камней в двух кучах становится
В начальный момент в первой куче было
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное из таких
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. Изменять количество камней в большей куче не разрешается. Пусть, например, в начале игры в первой куче
Игра завершается, когда общее количество камней в двух кучах становится
В начальный момент в первой куче было 8 камней, а во второй —
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное и максимальное из таких значений S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани.
В ответе запишите сначала минимальное значение, затем максимальное.