Два игрока играют в следующую игру: перед игроками лежит куча из 10 монет. Игроки ходят по очереди. За один ход игрок может добавить в кучу 7 или 10 монет. У каждого игрока, чтобы…

Задача имеет цель "Понять": разложим решение пошагово, затем покажем дерево и сделаем вывод.

1. Общий подход

• Победная/проклятая позиция: позиция n монет (где n < 27) считается выигрышной (N), если есть ход к проигрышной позиции (P). Позиция с n ≥ 27 считается терминальной и проигрышной для игрока, который должен ходить дальше.
• Рассчитаем назад от порога 27, где любая попытка сделать ход ≧ 27 завершается победой ходившего игрока, то есть переход к такой позиции считается проигрышной для следующего игрока.
• Вычислим статусы для n = 26, 25, …, 10. В итоге окажется, что n = 10 — проигрывающая позиция (P), значит второй игрок выигрывает при идеальной игре.

2. Расчёт статусов по шагам

• n ≥ 27: терминальные, P (нет хода).
• 26: ход +7 → 33 (терминал), ход +10 → 36 (терминал). Есть ход к P → 26 — N.
• 25: оба хода приводят к терминалу → N.
• 24: оба хода приводят к терминалу → N.
• 23: оба хода приводят к терминалу → N.
• 22: оба хода приводят к терминалу → N.
• 21: оба хода приводят к терминалу → N.
• 20: +7 → 27 (терминал), +10 → 30 (терминал) → оба хода к терминалу → N.
• 19: +7 → 26 (N), +10 → 29 (терминал). Есть ход к P (терминал) → 19 — N.
• 18: +7 → 25 (N), +10 → 28 (терминал) → есть ход к P → 18 — N.
• 17: +7 → 24 (N), +10 → 27 (терминал) → есть ход к P → 17 — N.
• 16: +7 → 23 (N), +10 → 26 (N) → оба хода в N → 16 — P.
• 15: +7 → 22 (N), +10 → 25 (N) → 15 — P.
• 14: +7 → 21 (N), +10 → 24 (N) → 14 — P.
• 13: +7 → 20 (N), +10 → 23 (N) → 13 — P.
• 12: +7 → 19 (N), +10 → 22 (N) → 12 — P.
• 11: +7 → 18 (N), +10 → 21 (N) → 11 — P.
• 10: +7 → 17 (N), +10 → 20 (N) → оба хода в N → 10 — P.

Итог: стартовая позиция 10 — проигрывающая для того, кто ходит, значит второй игрок выигрывает при идеальной игре.

3. Дерево этой игры Начальная позиция: 10 coins.

Дерево (первая ветка — ход первого игрока; помечены конечные состояния, где reached ≥ 27):

10 ├── 17 │ ├── 24 │ │ ├── 31 (конец, победитель: первый игрок, который сделал ход на 31) │ │ └── 34 (конец, победитель: первый игрок) │ └── 27 (конец, победитель: второй игрок) └── 20 ├── 27 (конец, победитель: второй игрок) └── 30 (конец, победитель: второй игрок)

Пояснения к дереву:

• Из 10 первый ход может быть к 17 или к 20.
• Из 17 следующий ход может быть к 24 или к 27. Ход к 27 завершает игру и выигрывает игрок, сделавший этот ход (второй игрок). Если же выбирается 24, затем второй ход может завершиться переходом к 31 или 34 — также заканчиваются победой того игрока, который сделал ход на 31/34.
• Из 20 следующий ход может быть к 27 или к 30 — оба варианта завершают игру и выигрывает тот, кто сделал этот ход (второй игрок).

4. Вывод При идеальной игре второй игрок имеет выигрышную стратегию. Любой первый ход первого игрока (к 17 или к 20) позволяет второму игроку завершить игру на следующем ходу или привести к позиции, из которой он обязательно выиграет в дальнейшем. Поэтому победитель при безошибочной игре: второй игрок, начинающий вторым ходом.