При этом нельзя повторять ход, который этот же игрок делал на
Условие
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который этот же игрок делал на предыдущем ходу. Повторять чужие ходы и свои более старые ходы разрешается.
Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил два камня), то следующим ходом Ваня может получить 6, 7 или 10 камней. Если Ваня добавил один камень и получил 6 камней, то вторым ходом Петя может получить 7 или 12 камней. Получить 8 камней Петя не может, так как для этого нужно добавить 2 камня, а Петя делал это на предыдущем ходу.
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается, когда количество камней в куче становится не менее 21. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 21 или больше камней. В начальный момент в куче было S камней, 1 ⩽ S ⩽ 20.Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите два значения S, при которых у Вани есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.В ответе запишите найденные значения в порядке возрастания: сначала меньшее, затем большее.
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Разбор задачи целиком открывается после входа.
Осталось ещё 15 шагов
Своим первым ходом Петя может получить…
В позиции 12 Ваня своим первым ходом…
Своим первым ходом Петя может получить…
В позиции 14 Ваня своим первым ходом…
Приведём другое решение на языке Python…
and x >= 21: return 1 elif h == 5 and x <…
or f(x + 2, h + 1, p…
or f(x * 2, h + 1, p…
# стратегия победителя elif h == 4: if v ==…
== 1: print("Задача 20:", x) # Исключаем…
# стратегия победителя else: return f(x +…
and f(x + 2, h +…
and f(x * 2, h +…
# стратегия проигравшего(любой ход) for x in…
== 1: print("Победа Вани первым ходом:", x)…
Бесплатно · займёт минуту