Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. В игре разрешено делать следующие ходы:
— добавить в кучу один камень;
— если количество камней в куче чётно, добавить половину имеющегося количества;
— если количество камней в куче кратно трём, добавить треть имеющегося количества;
— если количество камней в куче не кратно ни двум, ни трём, удвоить кучу.
Например, если в куче
Игра завершается, когда количество камней в куче
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой
В начале игры в куче было
Укажите минимальное
Такое значение S — 66. Своим первым ходом Петя может получить
Приведём решение на языке Python.
def f(x, h):
if x >= 132:
return h % 2 == 0
if h == 0:
return 0
c = [f(x + 1, h - 1)]
if x % 2 == 0:
c += [f(x *3 // 2, h - 1)]
if x % 3 == 0:
c += [f(x *4 // 3, h - 1)]
if x % 2 != 0 and x % 3 != 0:
c += [f(x * 2, h - 1)]
return any (c) if h % 2 != 0 else all(c)
for x in range(1, 132):
if f(x, 2) == 1:
print("Задача 19: ", x)
break
Ответ: 66.
Приведём решение Михаила Глинского на языке Python.
def f(x,n):
if n==2 and x>=132:
return 1
if n==2 and x<132:
return 0
if n==1 and x>=132:
return 0
else:
a=0
if x%2==0:
a=x//2
if x%3==0:
a=x//3
if x%2!=0 and x%3!=0 :
a=x
if n%2==0:
return f(x+1,n+1) and f(x+a,n+1)
if n%2==1:
return f(x+1,n+1) or f(x+a,n+1)
for s in range(1,132):
if f(s,0):
print(s)
break
Для игры, описанной
В ответе запишите найденные значения в порядке возрастания.
Ответ:
Для игры, описанной