ЕГЭ–2026, информатика: задания, ответы, решения

Тип 21 № 40737 Добавить в вариант

i

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который только что сделал второй игрок.

Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил 2 камня), то следующим ходом Ваня может получить 6 или 10 камней. Получить 7 камней Ваня не может, так как для этого нужно добавить 2 камня, а такой ход только что сделал Петя.

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 34. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 34 или больше камней. В начальный момент в куче было S камней; 1 ⩽ S ⩽ 33.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Найдите значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.

Аналоги к заданию № 40737: 40996 46977 47018 Все

Решение · Помощь

1

Тип 19 № 40735 Добавить в вариант

i

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который только что сделал второй игрок.

Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил 2 камня), то следующим ходом Ваня может получить 6 или 10 камней. Получить 7 камней Ваня не может, так как для этого нужно добавить 2 камня, а такой ход только что сделал Петя.

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 34. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 34 или больше камней. В начальный момент в куче было S камней, 1 ⩽ S ⩽ 33.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Аналоги к заданию № 40735: 40994 47016 Все

Решение · Помощь

2

Тип 20 № 40736 Добавить в вариант

i

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который только что сделал второй игрок.

Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил 2 камня), то следующим ходом Ваня может получить 6 или 10 камней. Получить 7 камней Ваня не может, так как для этого нужно добавить 2 камня, а такой ход только что сделал Петя.

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 34. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 34 или больше камней. В начальный момент в куче было S камней, 1 ⩽ S ⩽ 33.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Существует несколько таких значений S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найдите наименьшее и наибольшее из таких значений S.

В ответе запишите сначала наименьшее, затем наибольшее значение.

Аналоги к заданию № 40736: 40995 47017 Все

Решение · Помощь

Тип 21 № 40996 Добавить в вариант

i

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который только что сделал второй игрок.

Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил 2 камня), то следующим ходом Ваня может получить 6 или 10 камней. Получить 7 камней Ваня не может, так как для этого нужно добавить 2 камня, а такой ход только что сделал Петя.

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 50. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 50 или больше камней. В начальный момент в куче было S камней, 1 ⩽ S ⩽ 49.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Найдите значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.

Решение.

Такое значение S  — 11. При S  =  11 Петя своим первым ходом может получить одну из трёх позиций: 12, 13 или 22. В первом и третьем случаях Ваня может получить позицию 24, удвоив количество камней в куче или добавив два камня в кучу соответственно. Тогда, вне зависимости от хода Пети, Ваня побеждает своим вторым ходом.

В ситуации, когда после первого хода Пети в куче становится 13 камней, Ваня может удвоить количество камней в куче и получить позицию 26. Тогда Петя своим вторым ходом может получить позиции 27 и 28 (позицию 52 Ваня получить не может, поскольку нельзя повторять ход, который только что сделал второй игрок). Своим вторым ходом Ваня может удвоить количество камней в куче и выиграть игру.

Ответ: 11.

Примечание.

Обращаем внимание тех читателей, у которых получается ответ 21, на то, что по условию нельзя повторять ход предыдущего игрока.

Приведем решение Юрия Красильникова на языке Python.

def move(n,lim,s,t):

player = 2-n%2

rival = 3-player

if s >= 50: return rival

if n > lim: return 0

pos = [(s+1,0),(s+2,1),(s*2,2)]

if len(t) > 0: del pos[t[-1]]

res = [move(n+1,lim,x[0],t+[x[1]]) 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,50) if move(1,2,s,[])==2])

print('#20:',*[s for s in range(1,50) if move(1,1,s,[])==0 and move(1,3,s,[])==1])

print('#21:',*[s for s in range(1,50) if move(1,2,s,[])==0 and move(1,4,s,[])==2])

Аналоги к заданию № 40737: 40996 46977 47018 Все

Решение · Помощь

1

Тип 19 № 40994 Добавить в вариант

i

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который только что сделал второй игрок.

Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил 2 камня), то следующим ходом Ваня может получить 6 или 10 камней. Получить 7 камней Ваня не может, так как для этого нужно добавить 2 камня, а такой ход только что сделал Петя.

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 50. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 50 или больше камней. В начальный момент в куче было S камней, 1 ⩽ S ⩽ 49.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Решение.

Такое значение S  — 24. Своим первым ходом Петя может получить позиции 25, 26 и 48. В первых двух случаях Ваня удваивает количество камней в куче, в третьем случае Ваня добавляет в кучу два камня. Во всех случаях Ваня выигрывает своим первым ходом.

Ответ: 24.

Приведём другое решение на языке Python.

Для контроля ходов игроков заведём переменную m.

Если m = 1, то это действие x + 1

Если m = 2, то это действие x + 2

Если m = 3, то это действие x * 2

Таким образом, можно исключать ходы, которые уже были сделаны, не включая их в возвращаемые значения функции.

def f(x, h, m):

if h == 3 and x >= 50:

return 1

elif h == 3 and x < 50:

return 0

elif x >= 50 and h < 3:

return 0

else:

if h % 2 == 0:

if h == 2:

if m == 1:

return f(x + 2, h + 1, m) or f(x * 2, h + 1, m)

elif m == 2:

return f(x + 1, h + 1, m) or f(x * 2, h + 1, m)

elif m == 3:

return f(x + 1, h + 1, m) or f(x + 2, h + 1, m)

else:

return f(x + 1, h + 1, 1) and f(x + 2, h + 1, 2) and f(x * 2, h + 1, 3)

for x in range(1, 50):

if f(x, 1, 0) == 1:

print("Задача 19:", x)

break

Приведем решение Юрия Красильникова на языке Python.

def move(n,lim,s,t):

player = 2-n%2

rival = 3-player

if s >= 50: return rival

if n > lim: return 0

pos = [(s+1,0),(s+2,1),(s*2,2)]

if len(t) > 0: del pos[t[-1]]

res = [move(n+1,lim,x[0],t+[x[1]]) 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,50) if move(1,2,s,[])==2])

print('#20:',*[s for s in range(1,50) if move(1,1,s,[])==0 and move(1,3,s,[])==1])

print('#21:',*[s for s in range(1,50) if move(1,2,s,[])==0 and move(1,4,s,[])==2])

Аналоги к заданию № 40735: 40994 47016 Все

Решение · Помощь

2

Тип 20 № 40995 Добавить в вариант

i

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который только что сделал второй игрок.

Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил 2 камня), то следующим ходом Ваня может получить 6 или 10 камней. Получить 7 камней Ваня не может, так как для этого нужно добавить 2 камня, а такой ход только что сделал Петя.

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 50. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 50 или больше камней. В начальный момент в куче было S камней, 1 ⩽ S ⩽ 49.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Существует несколько таких значений S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найдите наименьшее и наибольшее из таких значений S.

В ответе запишите сначала наименьшее, затем наибольшее значение.

Решение.

Рассмотрим наименьшее значение S  =  12. Своим первым ходом Петя может получить позицию 24, удвоив количество камней в куче. После этого Ваня может получить позиции 25 и 26 (позицию 48 Ваня получить не может, поскольку нельзя повторять ход, который только что сделал второй игрок). В любой из позиций Петя может удвоить количество камней в куче и выиграть своим вторым ходом.

Наибольшее значение S  — 23. Своим первым ходом Петя добавляет в кучу один камень и получает позицию 24. После этого Ваня может получить позиции 26 и 48 (позицию 25 Ваня получить не может, поскольку нельзя повторять ход, который только что сделал второй игрок). В первом случае Петя может удвоить количество камней в куче, во втором случае Петя может добавить в кучу два камня. В обеих ситуациях Петя побеждает своим вторым ходом.

Таким образом, ответ  — 1223.

Ответ: 1223.

Приведем решение Юрия Красильникова на языке Python.

def move(n,lim,s,t):

player = 2-n%2

rival = 3-player

if s >= 50: return rival

if n > lim: return 0

pos = [(s+1,0),(s+2,1),(s*2,2)]

if len(t) > 0: del pos[t[-1]]

res = [move(n+1,lim,x[0],t+[x[1]]) 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,50) if move(1,2,s,[])==2])

print('#20:',*[s for s in range(1,50) if move(1,1,s,[])==0 and move(1,3,s,[])==1])

print('#21:',*[s for s in range(1,50) if move(1,2,s,[])==0 and move(1,4,s,[])==2])

Аналоги к заданию № 40736: 40995 47017 Все

Решение · Помощь

Тип 21 № 46977 Добавить в вариант

i

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который этот же игрок делал на предыдущем ходу. Повторять чужие ходы и свои более старые ходы разрешается.

Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил два камня), то следующим ходом Ваня может получить 6, 7 или 10 камней. Если Ваня добавил один камень и получил 6 камней, то вторым ходом Петя может получить 7 или 12 камней. Получить 8 камней Петя не может, так как для этого нужно добавить 2 камня, а Петя делал это на предыдущем ходу.

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается, когда количество камней в куче становится не менее 21. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 21 или больше камней. В начальный момент в куче было S камней, 1 ⩽ S ⩽ 20.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Укажите наименьшее значение S, при котором Петя не может выиграть за один ход, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом.

Решение.

Такое значение S  — 8. Своим первым ходом Петя может получить позицию 10. Ваня своим первым ходом может получить позиции 11, 12 и 20. Во всех случаях Петя увеличивает количество камней в куче в два раза и выигрывает своим вторым ходом.

Ответ: 8.

Приведём другое решение на языке Python.

Для контроля ходов игроков заведём переменную m.

Если m = 1, то это действие x + 1

Если m = 2, то это действие x + 2

Если m = 3, то это действие x * 2

Таким образом, можно исключать ходы, которые уже были сделаны, не включая их в возвращаемые значения функции.

def f(x, h, m):

if h == 4 and x >= 21:

return 1

elif h == 4 and x < 21:

return 0

elif x >= 21 and h < 4:

return 0

else:

if h % 2 != 0:

if h == 1:

return f(x + 1, h + 1, 1) or f(x + 2, h + 1, 2) or f(x * 2, h + 1, 3) # стратегия победителя

elif h == 3:

if m == 1:

return f(x + 2, h + 1, m) or f(x * 2, h + 1, m)

elif m == 2:

return f(x + 1, h + 1, m) or f(x * 2, h + 1, m)

elif m == 3:

return f(x + 1, h + 1, m) or f(x + 2, h + 1, m)

else:

return f(x + 1, h + 1, m) and f(x + 2, h + 1, m) and f(x * 2, h + 1, m)

for x in range(1, 21):

if f(x, 1, 0) == 1:

print("Задача 19:", x)

break

Приведем решение Юрия Красильникова на языке Python.

def move(n,lim,s,t):

player = 2-n%2

rival = 3-player

if s>= 21: return rival

if n > lim: return 0

pos = [(s+1,0),(s+2,1),(s*2,2)]

if len(t) > 1: del pos[t[-2]]

res = [move(n+1,lim,x[0],t+[x[1]]) 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,21) if move(1,1,s,[])==0 and move(1,3,s,[])==1])

print('#20:',*[s for s in range(1,21) if move(1,2,s,[])==0 and move(1,4,s,[])==2])

print('#21:',*[s for s in range(1,21) if move(1,3,s,[])==0 and move(1,5,s,[])==1])

Приведем решение Рустама Ханнанова (Ижевск) на языке Python.

from functools import lru_cache

def m(s):

A = []

x,steps = s

if steps[0] != '+1':

q = (steps[1],'+1')

A.append((x + 1,q))

if steps[0] != '+2':

q = (steps[1],'+2')

A.append((x + 2,q))

if steps[0] != '*2':

q = (steps[1],'*2')

A.append((x * 2,q))

return A

@lru_cache(None)

def g(s):

x, steps = s

if x >= 21: return 'w'

if any(g(x) == 'w' for x in m(s)): return 'p1'

if all(g(x) == 'p1' for x in m(s)): return 'w1'

if any(g(x) == 'w1' for x in m(s)): return 'p2'

if all(g(x) == 'p1' or g(x) == 'p2' for x in m(s)): return 'w2'

if any(g(x) == 'w1' or g(x) == 'w2' for x in m(s)): return 'p3'

if all(g(x) == 'p1' or g(x) == 'p2' or g(x) == 'p3' for x in m(s)): return 'w3'

for s in range(1,21):

h = (s,(0,0))

if g(h) == 'p2':

print(s)

Аналоги к заданию № 40737: 40996 46977 47018 Все

Решение · Помощь

1

Тип 20 № 46978 Добавить в вариант

i

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который этот же игрок делал на предыдущем ходу. Повторять чужие ходы и свои более старые ходы разрешается.

Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил два камня), то следующим ходом Ваня может получить 6, 7 или 10 камней. Если Ваня добавил один камень и получил 6 камней, то вторым ходом Петя может получить 7 или 12 камней. Получить 8 камней Петя не может, так как для этого нужно добавить 2 камня, а Петя делал это на предыдущем ходу.

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается, когда количество камней в куче становится не менее 21. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 21 или больше камней. В начальный момент в куче было S камней, 1 ⩽ S ⩽ 20.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Укажите два значения S, при которых у Вани есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.

В ответе запишите найденные значения в порядке возрастания: сначала меньшее, затем большее.

Решение.

Рассмотрим значение S  =  6. Своим первым ходом Петя может получить позиции 7, 8 и 12. В позиции 12 Ваня своим первым ходом удваивает количество камней в куче и выигрывает своим первым ходом. Из позиции 7 Ваня своим первым ходом может получить позицию 9, после чего Петя своим вторым ходом может получить позиции 11 и 18 (позицию 10 Петя получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). В обоих случаях Ваня своим вторым ходом удваивает количество камней в куче и выигрывает своим вторым ходом. Из позиции 8 Ваня может получить позицию 10, после чего Петя своим вторым ходом может получить позиции 11 и 20 (позицию 12 Петя получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). В обоих случаях Ваня своим вторым ходом удваивает количество камней в куче и выигрывает своим вторым ходом.

Второе значение S  — 7. Своим первым ходом Петя может получить позиции 8, 9 и 14. В позиции 14 Ваня своим первым ходом удваивает количество камней в куче и выигрывает своим первым ходом. Из позиции 8 Ваня своим первым ходом может получить позицию 9, после чего Петя своим вторым ходом может получить позиции 11 и 18 (позицию 10 Петя получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). В обоих случаях Ваня своим вторым ходом удваивает количество камней в куче и выигрывает своим вторым ходом. Из позиции 9 Ваня может получить позицию 10, после чего Петя своим вторым ходом может получить позиции 11 и 20 (позицию 12 Петя получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). В обоих случаях Ваня своим вторым ходом удваивает количество камней в куче и выигрывает своим вторым ходом.

Ответ: 67.

Приведём другое решение на языке Python.

Заведём переменные, отслеживающие сделанные ходы.

Так можно исключать ходы, которые уже были сделаны, не включая их в возвращаемые значения функции.

Сначала найдём для победы Вани первым или вторым ходом, а затем исключим победу Вани только первым ходом.

def f(x, h, p, v):

if (h == 5 or h == 3) and x >= 21:

return 1

elif h == 5 and x < 21:

return 0

elif x >= 21 and h < 5:

return 0

else:

if h % 2 == 0:

if h == 2:

return f(x + 1, h + 1, p, 1) or f(x + 2, h + 1, p, 2) or f(x * 2, h + 1, p, 3) # стратегия победителя

elif h == 4:

if v == 1:

return f(x + 2, h + 1, p, v) or f(x * 2, h + 1, p, v)

elif v == 2:

return f(x + 1, h + 1, p, v) or f(x * 2, h + 1, p, v)

elif v == 3:

return f(x + 1, h + 1, p, v) or f(x + 2, h + 1, p, v)

else: # Петин ход

if h == 1:

return f(x + 1, h + 1, 1, v) and f(x + 2, h + 1, 2, v) and f(x * 2, h + 1, 3, v) # стратегия победителя

elif h == 3:

if p == 1:

return f(x + 2, h + 1, p, v) and f(x * 2, h + 1, p, v)

elif p == 2:

return f(x + 1, h + 1, p, v) and f(x * 2, h + 1, p, v)

elif p == 3:

return f(x + 1, h + 1, p, v) and f(x + 2, h + 1, p, v)

for x in range(1, 21):

if f(x, 1, 0, 0) == 1:

print("Задача 20:", x)

# Исключаем победу Вани только первым ходом

def f(x, h):

if h == 3 and x >= 21:

return 1

elif h == 3 and x < 21:

return 0

elif x >= 21 and h < 3:

return 0

else:

if h % 2 == 0:

return f(x + 1, h + 1) or f(x + 2, h + 1) or f(x * 2, h + 1) # стратегия победителя

else:

return f(x + 1, h + 1) and f(x + 2, h + 1) and f(x * 2, h + 1) # стратегия проигравшего(любой ход)

for x in range(1, 21):

if f(x, 1) == 1:

print("Победа Вани первым ходом:", x)

Приведем решение Юрия Красильникова на языке Python.

def move(n,lim,s,t):

player = 2-n%2

rival = 3-player

if s>= 21: return rival

if n > lim: return 0

pos = [(s+1,0),(s+2,1),(s*2,2)]

if len(t) > 1: del pos[t[-2]]

res = [move(n+1,lim,x[0],t+[x[1]]) 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,21) if move(1,1,s,[])==0 and move(1,3,s,[])==1])

print('#20:',*[s for s in range(1,21) if move(1,2,s,[])==0 and move(1,4,s,[])==2])

print('#21:',*[s for s in range(1,21) if move(1,3,s,[])==0 and move(1,5,s,[])==1])

Решение · Помощь

2

Тип 21 № 46979 Добавить в вариант

i

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который этот же игрок делал на предыдущем ходу. Повторять чужие ходы и свои более старые ходы разрешается.

Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил два камня), то следующим ходом Ваня может получить 6, 7 или 10 камней. Если Ваня добавил один камень и получил 6 камней, то вторым ходом Петя может получить 7 или 12 камней. Получить 8 камней Петя не может, так как для этого нужно добавить 2 камня, а Петя делал это на предыдущем ходу.

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается, когда количество камней в куче становится не менее 21. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 21 или больше камней. В начальный момент в куче было S камней, 1 ⩽ S ⩽ 20.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Найдите наибольшее значение S, при котором у Пети есть выигрышная стратегия, позволяющая ему выиграть третьим ходом при любой игре Вани, но у Пети нет стратегии, которая позволяла бы ему гарантированно выиграть первым или вторым ходом.

Решение.

Такое значение S  — 5. При S  =  5 Петя своим первым ходом может получить позицию 7. Ваня своим первым ходом может получить одну из позиций 8, 9 и 14. В позиции 14 Петя своим вторым ходом удваивает количество камней в куче и выигрывает своим вторым ходом. В позициях 8 и 9 Петя своим вторым ходом добавляет в кучу один камень и получает позиции 9 и 10 соответственно. В позиции 9 Ваня своим вторым ходом может получить позиции 11 и 18 (позицию 10 Ваня получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). В позиции 10 Ваня своим вторым ходом может получить позиции 11 и 20 (позицию 12 Ваня получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). Во всех четырёх случаях Петя удваивает количество камней в куче и выигрывает своим третьим ходом.

Ответ: 5.

Приведём другое решение на языке Python.

Заведём переменные, отслеживающие сделанные ходы.

Так можно исключать ходы, которые уже были сделаны, не включая их в возвращаемые значения функции.

Сначала найдём для победы Вани первым или вторым ходом, а затем исключим победу Вани только первым ходом.

# Победа Пети первым или вторым, или третьим ходом

def f(x, h, p, v):

if (h == 2 or h == 4 or h == 6) and x >= 21:

return 1

elif h == 6 and x < 21:

return 0

elif x >= 21 and h < 6:

return 0

else:

if h % 2 == 0:

if h == 2:

return f(x + 1, h + 1, p, 1) and f(x + 2, h + 1, p, 2) and f(x * 2, h + 1, p, 3) # стратегия проигравшего

elif h == 4:

if v == 1:

return f(x + 2, h + 1, p, v) and f(x * 2, h + 1, p, v)

elif v == 2:

return f(x + 1, h + 1, p, v) and f(x * 2, h + 1, p, v)

elif v == 3:

return f(x + 1, h + 1, p, v) and f(x + 2, h + 1, p, v)

else: # Петин ход

if h == 1:

return f(x + 1, h + 1, 1, v) or f(x + 2, h + 1, 2, v) or f(x * 2, h + 1, 3, v) # стратегия победителя

elif h == 3:

if p == 1:

return f(x + 2, h + 1, 2, v) or f(x * 2, h + 1, 3, v)

elif p == 2:

return f(x + 1, h + 1, 1, v) or f(x * 2, h + 1, 3, v)

elif p == 3:

return f(x + 1, h + 1, 1, v) or f(x + 2, h + 1, 2, v)

elif h == 5:

if p == 1:

return f(x + 2, h + 1, p, v) or f(x * 2, h + 1, p, v)

elif p == 2:

return f(x + 1, h + 1, p, v) or f(x * 2, h + 1, p, v)

elif p == 3:

return f(x + 1, h + 1, p, v) or f(x + 2, h + 1, p, v)

for x in range(1, 21):

if f(x, 1, 0, 0) == 1:

print("Задача 21:", x)

# Исключаем победу Пети только первым ходом

def f(x, h):

if h == 2 and x >= 21:

return 1

elif h == 2 and x < 21:

return 0

elif x >= 21 and h < 2:

return 0

else:

if h % 2 != 0:

return f(x + 1, h + 1) or f(x + 2, h + 1) or f(x * 2, h + 1) # стратегия победителя

else:

return f(x + 1, h + 1) and f(x + 2, h + 1) and f(x * 2, h + 1) # стратегия проигравшего(любой ход)

for x in range(1, 21):

if f(x, 1) == 1:

print("Победа Пети первым ходом:", x)

# Победа Пети вторым ходом

def f(x, h, m):

if h == 4 and x >= 21:

return 1

elif h == 4 and x < 21:

return 0

elif x >= 21 and h < 4:

return 0

else:

if h % 2 != 0:

if h == 1:

return f(x + 1, h + 1, 1) or f(x + 2, h + 1, 2) or f(x * 2, h + 1, 3) # стратегия победителя

elif h == 3:

if m == 1:

return f(x + 2, h + 1, m) or f(x * 2, h + 1, m)

elif m == 2:

return f(x + 1, h + 1, m) or f(x * 2, h + 1, m)

elif m == 3:

return f(x + 1, h + 1, m) or f(x + 2, h + 1, m)

else:

return f(x + 1, h + 1, m) and f(x + 2, h + 1, m) and f(x * 2, h + 1, m)

for x in range(1, 21):

if f(x, 1, 0) == 1:

print("Победа Пети вторым ходом:", x)

Приведем решение Юрия Красильникова на языке Python.

def move(n,lim,s,t):

player = 2-n%2

rival = 3-player

if s>= 21: return rival

if n > lim: return 0

pos = [(s+1,0),(s+2,1),(s*2,2)]

if len(t) > 1: del pos[t[-2]]

res = [move(n+1,lim,x[0],t+[x[1]]) 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,21) if move(1,1,s,[])==0 and move(1,3,s,[])==1])

print('#20:',*[s for s in range(1,21) if move(1,2,s,[])==0 and move(1,4,s,[])==2])

print('#21:',*[s for s in range(1,21) if move(1,3,s,[])==0 and move(1,5,s,[])==1])

Решение · Помощь

Тип 21 № 47018 Добавить в вариант

i

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который этот же игрок делал на предыдущем ходу. Повторять чужие ходы и свои более старые ходы разрешается.

Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил два камня), то следующим ходом Ваня может получить 6, 7 или 10 камней. Если Ваня добавил один камень и получил 6 камней, то вторым ходом Петя может получить 7 или 12 камней. Получить 8 камней Петя не может, так как для этого нужно добавить 2 камня, а Петя делал это на предыдущем ходу.

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней; 1 ⩽ S ⩽ 28.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Найдите наибольшее значение S, при котором у Пети есть выигрышная стратегия, позволяющая ему выиграть третьим ходом при любой игре Вани, но у Пети нет стратегии, которая позволяла бы ему гарантированно выиграть первым или вторым ходом.

Решение.

Такое значение S  — 9. При S  =  9 Петя своим первым ходом может получить позицию 11. Ваня своим первым ходом может получить одну из позиций 12, 13 и 22. В позиции 22 Петя своим вторым ходом удваивает количество камней в куче и выигрывает своим вторым ходом. В позициях 12 и 13 Петя своим вторым ходом добавляет в кучу один камень и получает позиции 13 и 14 соответственно. В позиции 13 Ваня своим вторым ходом может получить позиции 15 и 26 (позицию 14 Ваня получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). В позиции 14 Ваня своим вторым ходом может получить позиции 15 и 28 (позицию 16 Ваня получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). Во всех четырёх случаях Петя удваивает количество камней в куче и выигрывает своим третьим ходом.

Ответ: 9.

Приведём другое решение на языке Python.

Заведём переменные, отслеживающие сделанные ходы.

Так можно исключать ходы, которые уже были сделаны, не включая их в возвращаемые значения функции.

Сначала найдём стратегии победы Пети первым, вторым или третьим ходом.

Далее исключим победу Пети только первым и только вторым ходом.

# Победа Пети первым или вторым, или третьим ходом

def f(x, h, p, v):

if (h == 2 or h == 4 or h == 6) and x >= 29:

return 1

elif h == 6 and x < 29:

return 0

elif x >= 29 and h < 6:

return 0

else:

if h % 2 == 0:

if h == 2:

return f(x + 1, h + 1, p, 1) and f(x + 2, h + 1, p, 2) and f(x * 2, h + 1, p, 3) # стратегия проигравшего

elif h == 4:

if v == 1:

return f(x + 2, h + 1, p, v) and f(x * 2, h + 1, p, v)

elif v == 2:

return f(x + 1, h + 1, p, v) and f(x * 2, h + 1, p, v)

elif v == 3:

return f(x + 1, h + 1, p, v) and f(x + 2, h + 1, p, v)

else: # Петин ход

if h == 1:

return f(x + 1, h + 1, 1, v) or f(x + 2, h + 1, 2, v) or f(x * 2, h + 1, 3, v) # стратегия победителя

elif h == 3:

if p == 1:

return f(x + 2, h + 1, 2, v) or f(x * 2, h + 1, 3, v)

elif p == 2:

return f(x + 1, h + 1, 1, v) or f(x * 2, h + 1, 3, v)

elif p == 3:

return f(x + 1, h + 1, 1, v) or f(x + 2, h + 1, 2, v)

elif h == 5:

if p == 1:

return f(x + 2, h + 1, p, v) or f(x * 2, h + 1, p, v)

elif p == 2:

return f(x + 1, h + 1, p, v) or f(x * 2, h + 1, p, v)

elif p == 3:

return f(x + 1, h + 1, p, v) or f(x + 2, h + 1, p, v)

for x in range(1, 29):

if f(x, 1, 0, 0) == 1:

print("Задача 21:", x)

# Исключаем победу Пети только первым ходом

def f(x, h):

if h == 2 and x >= 29:

return 1

elif h == 2 and x < 29:

return 0

elif x >= 29 and h < 2:

return 0

else:

if h % 2 != 0:

return f(x + 1, h + 1) or f(x + 2, h + 1) or f(x * 2, h + 1) # стратегия победителя

else:

return f(x + 1, h + 1) and f(x + 2, h + 1) and f(x * 2, h + 1) # стратегия проигравшего(любой ход)

for x in range(1, 29):

if f(x, 1) == 1:

print("Победа Пети первым ходом:", x)

# Победа Пети вторым ходом

def f(x, h, m):

if h == 4 and x >= 29:

return 1

elif h == 4 and x < 29:

return 0

elif x >= 29 and h < 4:

return 0

else:

if h % 2 != 0:

if h == 1:

return f(x + 1, h + 1, 1) or f(x + 2, h + 1, 2) or f(x * 2, h + 1, 3) # стратегия победителя

elif h == 3:

if m == 1:

return f(x + 2, h + 1, m) or f(x * 2, h + 1, m)

elif m == 2:

return f(x + 1, h + 1, m) or f(x * 2, h + 1, m)

elif m == 3:

return f(x + 1, h + 1, m) or f(x + 2, h + 1, m)

else:

return f(x + 1, h + 1, m) and f(x + 2, h + 1, m) and f(x * 2, h + 1, m)

for x in range(1, 29):

if f(x, 1, 0) == 1:

print("Победа Пети вторым ходом:", x)

Приведём решение Юрия Красильникова на языке Python.

def move(n,lim,s,t):

player = 2-n%2

rival = 3-player

if s >= 29:

return rival

if n > lim:

return 0

pos=[(s+1,0),(s+2,1),(s*2,2)]

if len(t) >= 2:

del pos[t[-2]]

res = [move(n+1,lim,p[0],t+[p[1]]) for p in pos]

if any([r==player for r in res]):

return player

if all([r==rival for r in res]):

return rival

return 0

print('#19:',*[s for s in range(1,29) if move(1,1,s,[])==0 and move(1,3,s,[])==1])

print('#20:',*[s for s in range(1,29) if move(1,2,s,[])==0 and move(1,4,s,[])==2])

print('#21:',*[s for s in range(1,29) if move(1,3,s,[])==0 and move(1,5,s,[])==1])

Аналоги к заданию № 40737: 40996 46977 47018 Все

Решение · Помощь

1

Тип 19 № 47016 Добавить в вариант

i

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который этот же игрок делал на предыдущем ходу. Повторять чужие ходы и свои более старые ходы разрешается.

Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил два камня), то следующим ходом Ваня может получить 6, 7 или 10 камней. Если Ваня добавил один камень и получил 6 камней, то вторым ходом Петя может получить 7 или 12 камней. Получить 8 камней Петя не может, так как для этого нужно добавить 2 камня, а Петя делал это на предыдущем ходу.

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней, 1 ⩽ S ⩽ 28.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Укажите наименьшее значение S, при котором Петя не может выиграть за один ход, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом.

Решение.

Такое значение S  — 12. Своим первым ходом Петя может получить позицию 14. Ваня своим первым ходом может получить позиции 15, 16 и 28. Во всех случаях Петя увеличивает количество камней в куче в два раза и выигрывает своим вторым ходом.

Ответ: 12.

Приведём другое решение на языке Python.

Для контроля ходов игроков заведём переменную m.

Если m  =  1, то это действие x + 1.

Если m  =  2, то это действие x + 2.

Если m  =  3, то это действие x · 2.

Таким образом, можно исключать ходы, которые уже были сделаны, не включая их в возвращаемые значения функции.

def f(x, h, m):

if h == 4 and x >= 29:

return 1

elif h == 4 and x < 29:

return 0

elif x >= 29 and h < 4:

return 0

else:

if h % 2 != 0:

if h == 1:

return f(x + 1, h + 1, 1) or f(x + 2, h + 1, 2) or f(x * 2, h + 1, 3) # стратегия победителя

elif h == 3:

if m == 1:

return f(x + 2, h + 1, m) or f(x * 2, h + 1, m)

elif m == 2:

return f(x + 1, h + 1, m) or f(x * 2, h + 1, m)

elif m == 3:

return f(x + 1, h + 1, m) or f(x + 2, h + 1, m)

else:

return f(x + 1, h + 1, m) and f(x + 2, h + 1, m) and f(x * 2, h + 1, m)

for x in range(1, 29):

if f(x, 1, 0) == 1:

print("Задача 19:", x)

break

Приведём решение Юрия Красильникова на языке Python.

def move(n,lim,s,t):

player = 2-n%2

rival = 3-player

if s >= 29:

return rival

if n > lim:

return 0

pos=[(s+1,0),(s+2,1),(s*2,2)]

if len(t) >= 2:

del pos[t[-2]]

res = [move(n+1,lim,p[0],t+[p[1]]) for p in pos]

if any([r==player for r in res]):

return player

if all([r==rival for r in res]):

return rival

return 0

print('#19:',*[s for s in range(1,29) if move(1,1,s,[])==0 and move(1,3,s,[])==1])

print('#20:',*[s for s in range(1,29) if move(1,2,s,[])==0 and move(1,4,s,[])==2])

print('#21:',*[s for s in range(1,29) if move(1,3,s,[])==0 and move(1,5,s,[])==1])

Аналоги к заданию № 40735: 40994 47016 Все

Решение · Помощь

2

Тип 20 № 47017 Добавить в вариант

i

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который этот же игрок делал на предыдущем ходу. Повторять чужие ходы и свои более старые ходы разрешается.

Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил два камня), то следующим ходом Ваня может получить 6, 7 или 10 камней. Если Ваня добавил один камень и получил 6 камней, то вторым ходом Петя может получить 7 или 12 камней. Получить 8 камней Петя не может, так как для этого нужно добавить 2 камня, а Петя делал это на предыдущем ходу.

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней, 1 ⩽ S ⩽ 28.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Укажите два значения S, при которых у Вани есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.

В ответе запишите найденные значения в порядке возрастания: сначала меньшее, затем большее.

Решение.

Рассмотрим значение S  =  10. Своим первым ходом Петя может получить позиции 11, 12 и 20. В позиции 20 Ваня своим первым ходом удваивает количество камней в куче и выигрывает своим первым ходом. Из позиции 11 Ваня своим первым ходом может получить позицию 13, после чего Петя своим вторым ходом может получить позиции 15 и 26 (позицию 114 Петя получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). В обоих случаях Ваня своим вторым ходом удваивает количество камней в куче и выигрывает своим вторым ходом. Из позиции 12 Ваня может получить позицию 14, после чего Петя своим вторым ходом может получить позиции 15 и 28 (позицию 16 Петя получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). В обоих случаях Ваня своим вторым ходом удваивает количество камней в куче и выигрывает своим вторым ходом.

Второе значение S  — 11. Своим первым ходом Петя может получить позиции 12, 13 и 22. В позиции 22 Ваня своим первым ходом удваивает количество камней в куче и выигрывает своим первым ходом. Из позиции 12 Ваня своим первым ходом может получить позицию 14, после чего Петя своим вторым ходом может получить позиции 16 и 28 (позицию 15 Петя получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). В обоих случаях Ваня своим вторым ходом удваивает количество камней в куче и выигрывает своим вторым ходом. Из позиции 13 Ваня может получить позицию 14, после чего Петя своим вторым ходом может получить позиции 15 и 28 (позицию 16 Петя получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). В обоих случаях Ваня своим вторым ходом удваивает количество камней в куче и выигрывает своим вторым ходом.

Ответ: 1011.

Приведём другое решение на языке Python.

Заведём переменные, отслеживающие сделанные ходы.

Так можно исключать ходы, которые уже были сделаны, не включая их в возвращаемые значения функции.

Сначала найдём для победы Вани первым или вторым ходом, а затем исключим победу Вани только первым ходом.

def f(x, h, p, v):

if (h == 5 or h == 3) and x >= 29:

return 1

elif h == 5 and x < 29:

return 0

elif x >= 29 and h < 5:

return 0

else:

if h % 2 == 0:

if h == 2:

return f(x + 1, h + 1, p, 1) or f(x + 2, h + 1, p, 2) or f(x * 2, h + 1, p, 3) # стратегия победителя

elif h == 4:

if v == 1:

return f(x + 2, h + 1, p, v) or f(x * 2, h + 1, p, v)

elif v == 2:

return f(x + 1, h + 1, p, v) or f(x * 2, h + 1, p, v)

elif v == 3:

return f(x + 1, h + 1, p, v) or f(x + 2, h + 1, p, v)

else: # Петин ход

if h == 1:

return f(x + 1, h + 1, 1, v) and f(x + 2, h + 1, 2, v) and f(x * 2, h + 1, 3, v) # стратегия победителя

elif h == 3:

if p == 1:

return f(x + 2, h + 1, p, v) and f(x * 2, h + 1, p, v)

elif p == 2:

return f(x + 1, h + 1, p, v) and f(x * 2, h + 1, p, v)

elif p == 3:

return f(x + 1, h + 1, p, v) and f(x + 2, h + 1, p, v)

for x in range(1, 29):

if f(x, 1, 0, 0) == 1:

print("Задача 20:", x)

# Исключаем победу Вани только первым ходом

def f(x, h):

if h == 3 and x >= 29:

return 1

elif h == 3 and x < 29:

return 0

elif x >= 29 and h < 3:

return 0

else:

if h % 2 == 0:

return f(x + 1, h + 1) or f(x + 2, h + 1) or f(x * 2, h + 1) # стратегия победителя

else:

return f(x + 1, h + 1) and f(x + 2, h + 1) and f(x * 2, h + 1) # стратегия проигравшего(любой ход)

Приведём решение Юрия Красильникова на языке Python.

def move(n,lim,s,t):

player = 2-n%2

rival = 3-player

if s >= 29:

return rival

if n > lim:

return 0

pos=[(s+1,0),(s+2,1),(s*2,2)]

if len(t) >= 2:

del pos[t[-2]]

res = [move(n+1,lim,p[0],t+[p[1]]) for p in pos]

if any([r==player for r in res]):

return player

if all([r==rival for r in res]):

return rival

return 0

print('#19:',*[s for s in range(1,29) if move(1,1,s,[])==0 and move(1,3,s,[])==1])

print('#20:',*[s for s in range(1,29) if move(1,2,s,[])==0 and move(1,4,s,[])==2])

print('#21:',*[s for s in range(1,29) if move(1,3,s,[])==0 and move(1,5,s,[])==1])

Аналоги к заданию № 40736: 40995 47017 Все

Решение · Помощь