Стратегии в игре с кучами
Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной куче в три раза. Игра заканчивается, как только суммарное количество камней в кучах становится не менее 74. Побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 6 камней, во второй — $S$ камней, где $1 \leq S \leq 67$.
Опишите выигрышные стратегии и постройте дерево партий, возможных при выигрышной стратегии Вани.
Условие как в банке ФИПИ — открыть и сверить
| Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 74. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет В начальный момент в первой куче было шесть камней, во второй куче
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Выполните следующие задания. Задание 1 а) Укажите все такие значения числа S, при которых Петя может выиграть за один ход. б) Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 2 Укажите такое значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: - Петя не может выиграть за один ход; - Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для указанного значения S опишите выигрышную стратегию Пети.
Задание 3 Укажите значение S, при котором одновременно выполняются два условия: - у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; - у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). В узлах дерева указывайте позиции, на рёбрах рекомендуется указывать ходы. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание. | ||
| |
Это задание с развёрнутым решением: ответом считается запись хода решения, а не строка. Напишите решение на бумаге и сравните с разбором — там каждый шаг с обоснованием.
Открыть разбор1Мягкая — с чего смотретьуровень 1 из 3
Для выигрыша одним ходом проверьте, может ли после добавления камня сумма стать не менее 74 или может ли утроение одной из куч дать сумму не менее 74.
2Наводящая — какие числа считатьуровень 2 из 3
Для анализа второго хода рассмотрите все четыре позиции, получаемые после первого хода: $(7,S)$, $(18,S)$, $(6,S+1)$ и $(6,3S)$.
3Прямая — фактически решениеуровень 3 из 3
Петя выигрывает первым ходом при $S \geq 23$. При $S=8$ Петя утроивает вторую кучу и получает позицию $(6,24)$; после любого хода Вани Петя завершает игру следующим ходом.