Условие:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: убрать из кучи два камня или убрать из кучи пять камней или уменьшить количество камней в куче в три раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 20 камней за один ход можно получить кучу из 18, 15 или 6 камней.
Игра завершается, когда количество камней в куче становится не более 19. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 19 или меньше камней. В начальный момент в куче было S камней, S≥ 20.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение Ѕ, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Решение:
Для решения данной задачи мы будем анализировать возможные состояния игры и определять, в каких из них игроки могут выиграть или проиграть. 1. Определим выигрышные и проигрышные позиции: - Если в куче 19 или меньше камней, игрок, который делает ход, выигрывает, так как он завершает игру. - Если в куче 20 камней, Петя может убрать 2, 5 или уменьшить в 3 раза, что приведет к состояниям 18, 15 или 6 камней соответственно. В любом из этих случаев Ваня сможет выиграть в следующем ходе. Таким образом, 20 — это проигрышная позиция для Пети. 2. Анализируем позиции от 21 до 24: - 21 камень: Петя м...