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

Задача имеет цель "Понять": разложим решение пошагово, затем покажем дерево и сделаем вывод. 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) позволяет второму игроку завершить игру на следующем ходу или привести к позиции, из которой он обязательно выиграет в дальнейшем. Поэтому победитель при безошибочной игре: второй игрок, начинающий вторым ходом.