Шешімі: Стратегии в игре с камнями
Два игрока, Петя и Ваня, играют в игру с кучей камней. За один ход игрок может добавить в кучу 2 или 3 камня либо увеличить количество камней в куче в 2 раза. Игра завершается, когда количество камней становится не менее 60. Побеждает игрок, сделавший последний ход. В начальный момент в куче было $S$ камней, где $1 \leq S \leq 59$.
Выполните три задания и во всех случаях обоснуйте ответ.
Задание 1. Укажите все значения $S$, при которых Петя может выиграть в один ход. Укажите также значение $S$, при котором Петя не может выиграть за один ход, но после любого его хода Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Задание 2. Укажите четыре значения $S$, при которых Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от хода Вани. Для каждого значения опишите выигрышную стратегию Пети.
Задание 3. Укажите значение $S$, при котором Ваня может выиграть первым или вторым ходом при любой игре Пети, но не может гарантированно выиграть первым ходом. Опишите выигрышную стратегию Вани и постройте дерево всех партий, возможных при этой стратегии. В узлах дерева указывайте количество камней, на рёбрах — ходы. Дерево не должно содержать партии, невозможные при реализации выигрышной стратегии Вани.
Шешім по шагам
8 қадамПетя выигрывает одним ходом, если хотя бы один из переходов $S+2$, $S+3$, $2S$ даёт не менее 60. При $1 \leq S \leq 59$ это выполняется при $S \geq 30$.
$$S \in \{30,31,\ldots,59\}$$Для задания 1б можно взять $S=28$. После хода Пети получаются позиции 30, 31 или 56. Из позиций 30 и 31 Ваня удваивает количество камней, а из позиции 56 также удваивает его и сразу получает не менее 60.
$$28 \to 30,31,56;\quad 30\to60,\ 31\to62,\ 56\to112$$Позиции 28 и 29 являются проигрышными для игрока, которому предстоит ходить: любой его ход переводит игру в позицию, из которой следующий игрок может выиграть одним ходом.
$$28\to30,31,56;\quad 29\to31,32,58$$В задании 2 Петя должен первым ходом получить 28 или 29. Это возможно для четырёх значений: $14\to28$ умножением на 2, $25\to28$ добавлением 3, $26\to28$ добавлением 2 или $29$ добавлением 3, $27\to29$ добавлением 2.
$$S\in\{14,25,26,27\}$$После получения позиции 28 или 29 любой ход Вани оставляет Петре возможность завершить игру следующим ходом: из 30, 31, 32 и 58 можно получить не менее 60 добавлением камней или удвоением, а из 56 — удвоением.
$$28\to30,31,56;\quad 29\to31,32,58$$Для задания 3 берём $S=19$. Петя не может выиграть первым ходом. После его ходов возможны позиции 21, 22 и 38. Из позиции 38 Ваня выигрывает сразу удвоением. Из позиций 21 и 22 Ваня переводит игру в проигрышную для Пети позицию 24.
$$19\to21,22,38;\quad 21\to24\ (+3);\quad 22\to24\ (+2)$$Из позиции 24 Петя может получить 26, 27 или 48. Ваня отвечает соответственно переходами 26\to28, 27\to29 и 48\to96. Позиции 28 и 29 являются проигрышными для Пети, а из 96 игра завершается.
$$24\to26,27,48;\quad 26\to28;\quad 27\to29;\quad 48\to96$$Дерево партий при стратегии Вани: $19\to21\to24$, $19\to22\to24$, $19\to38$; далее $24\to26\to28$, $24\to27\to29$, $24\to48\to96$. Из 28 Петя может получить 30, 31 или 56; первые два хода завершают игру, а из 56 Ваня удваивает количество камней. Из 29 Петя может получить 31, 32 или 58; первые два хода завершают игру, а из 58 Ваня удваивает количество камней.
$$28\to30,31,56;\quad 56\to112;\quad 29\to31,32,58;\quad 58\to116$$1а) $S=30,31,\ldots,59$. 1б) Например, $S=28$; Ваня после позиций 30, 31 и 56 удваивает количество камней. 2) $S=14,25,26,27$. 3) $S=19$; стратегия Вани: из 21 перейти в 24, из 22 перейти в 24, из 38 удвоить количество камней, затем после ходов из 24 переходить в 28, 29 или 96 соответственно.
Бұл жауап талдау нәтижесінде алынды, бірақ банктің ресми кілтімен тексерілген жоқ — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать, что при $S=29$ Петя может выиграть одним ходом: удвоение даёт только 58 камней.
В задании 2 указывать значения, для которых Петя уже выигрывает первым ходом.
Строить полное дерево игры вместо дерева только тех партий, которые возможны при выигрышной стратегии Вани.
Забывать, что после достижения 60 и более игра сразу заканчивается.