Question

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

Например, из кучи в 20 камней за один ход можно получить кучу из 17, 14 или 6 камней.

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

В начальный момент в куче было $S$ камней.

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

![Рисунок](https://ege.sdamgia.ru/formula/svg/1e/1e154d7bcf7c6409e346c9a4d0acc484.svg)

Accepted Answer

78

Answer

Идея решения: найти минимальное начальное количество камней, при котором первый игрок не может завершить игру за один ход, но любой его ход приводит в позицию, из которой второй игрок гарантированно выигрывает за один ход.

Определим две функции:
- `Win(n, m)` — может ли игрок выиграть за один ход из позиции с $m$ камнями, если осталось $n$ ходов до конца игры.
- `Lose(n, m)` — все ли ходы из позиции с $m$ камнями ведут в позиции, где противник выигрывает за один ход.

Позиция является выигрышной за один ход, если текущее количество камней не превышает 25 (игра уже завершена) или существует ход, ведущий в такую позицию.

Позиция является проигрышной (все ходы ведут в выигрышные для противника), если количество камней превышает 25 и все три возможных хода ведут в позиции, где противник выигрывает за один ход.

```python
def Win(n, m):
    return 0 if m <= 25 else any([
        Lose(n - 1, m - 3),
        Lose(n - 1, m - 6),
        Lose(n - 1, m // 3)
    ])

def Lose(n, m):
    return 1 if m <= 25 else 0 if not n else all([
        Win(n - 1, m - 3),
        Win(n - 1, m - 6),
        Win(n - 1, m // 3)
    ])

result = min(m for m in range(26, 100)
             if not Win(1, m) and Lose(2, m))
print(result)
```

Ищем минимальное значение $S$ в диапазоне от 26 до 100, такое что:
- `not Win(1, m)` — Петя не может выиграть за один ход;
- `Lose(2, m)` — при любом ходе Пети Ваня выигрывает за один ход.

Задание №19Алгоритмы и исполнителиЕГЭ по информатике