Передача хода

По правилам игры ничьих не бывает, поэтому либо первый игрок, либо второй имеет выигрышную стратегию. Первый игрок может “передать ход” второму, вычеркнув первым ходом Действительно, пусть второй вычёркивает число и все его делители. После этого хода вычеркнуты те числа, какие были бы вычеркнуты, если бы первый игрок первым своим ходом вычеркнул (и все его делители). Поэтому у второго игрока не может быть выигрышной стратегии: первый игрок, “передав ход”, может играть, следуя любой стратегии второго игрока. Значит, выигрышная стратегия есть у первого игрока.

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

Доказали, что первый игрок имеет выигрышную стратегию.

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

Докажем, что первый игрок может победить. Если у него есть выигрышная стратегия, то он, очевидно, уже побеждает.

Если же выигрышная стратегия есть у второго игрока, то первым ходом на месте Пети вычеркнем 1. Теперь на любой ход второго игрока будем отвечать согласно стратегии, которая будто бы есть у второго игрока.

Петя всегда так может сделать, поскольку его первый ход вообще никак не повлиял на игру: Вася своим первым ходом и так в любом случае вычеркнул бы 1. Значит, Петя победит.

Пусть Аня возьмёт камень из второй кучки (число 1 является делителем числа 2021), то есть число камней станет равным. Дальше её стратегия очень проста — повторять ход Пети в другой кучке. Если Петя нашёл делитель числа и забрал камней из какой-то кучи, то Аня может забрать камней из другой кучки (в которой перед её ходом тоже будет камней), поскольку число является делителем текущего числа камней в кучке, откуда брал Петя. Раз игра когда-нибудь закончится, то Аня победит.

Пусть первый игрок своим первым ходом положит монеты, а следующими ходами класть столько монет, чтобы сумма его монет и монет, положенных перед этим вторым игроком была равна В этом случае после третьего хода первого игрока в ряду будут лежать монет. Далее, как бы не сходил второй игрок своим третьим ходом и как бы после этого не сходил первый игрок монета будет положена первым игроком.

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

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

Тогда первым ходом за первую компанию поставим фонарь в правый нижний узел сетки. Этот фонарь не освещает других перекрестков, а любой другой фонарь освещает тот перекресток, на котором он стоит.

Теперь на каждый ход второго игрока будем отвечать согласно его выигрышной стратегии, то есть ставить фонарь в ту клетку, в которую при выигрышной стратегии на очередном шаге поставил бы фонарь второй игрок, если бы нашего первого хода не было.

Заметим, что такой ход всегда возможен: первый нами поставленный фонарь на игру не влияет. Ведь никакие другие перекрестки он не освещает, а тот перекресток, в котором он стоит, в любом случае сразу бы осветили, значит, в стратегии второго игрока не может быть хода, на котором он ставит фонарь в правый нижний узел. Поэтому у нас на месте первой компании всегда есть ход, значит, мы побеждаем.

Итак, мы получили противоречие, значит, у второй компании выигрышной стратегии нет. А так как при правильной игре всегда выигрывает одна и та же компания, то это первая компания, что мы и доказывали.

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

Докажем, что первый игрок может победить. Если у него есть выигрышная стратегия, то он, очевидно, уже побеждает.

Если же выигрышная стратегия есть у второго игрока, то первым ходом на месте первого возьмем одну карточку (с числом 1). Теперь на любой ход второго игрока будем отвечать согласно стратегии, которая будто бы есть у второго игрока.

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

Заметим, что игра конечна. Когда-нибудь наступит момент, когда все четные (по четному числу камней в каждой кучке) расположения будут уже использованы (встречались в процессе игры), а из любого нечетного расположения можно попасть только в четное (у нечетного числа есть только нечетные делители).

Тогда у одного из игроков точно есть выигрышная стратегия. Докажем, что второй не может иметь выигрышной стратегии. Предположим, что у второго есть выигрышная стратегия. Играя за первого игрока, сделаем такой первый шаг: переложим 1 камень из кучки 42 в кучку 30. Тогда второй игрок может походить единственным образом: переложить один камень из кучки 41 в кучку 31 (так как это простые числа, а расположение (30, 42) уже нельзя повторять). Тогда у второго есть ответные ходы на ходы первого из начальной позиции (32, 40) с учетом того, что нельзя попадать в позицию (30, 42), ведущие к выигрышу. Тогда, используя эту стратегию, начнем игру за первого по-другому: первым шагом переложим 2 камня из кучки 42 в кучку 30. Попадаем в игру с начальным условием (32, 40) с учетом того, что нельзя попадать в позицию (30, 42), где начинает ходить второй. Будем использовать выигрышную стратегию второго и победим. Значит, первый имеет выигрышную стратегию. Противоречие.

Доказали, что выигрышная стратегия обязательно только у первого.

Так как игра конечна, то один из игроков имеет выигрышную стратегию. Докажем, что второй не может иметь выигрышной стратегии. Предположим, что она у него есть, и будем играть за первого. Первым ходом отрежем одну клеточку в одном из уголков. Второй игрок обязательно вырежет прямоугольник, примыкающий к нашей вырезанной клетке. С этого момента у второго игрока есть ответные ходы на каждый наш ход, соответствующие выигрышной стратегии. Тогда можем начать игру по-другому: первым ходом вырежем прямоугольник, являющийся объединением уголка и вырезанного прямоугольника второго игрока на его ходе. Теперь будем отвечать на ходы второго по его же стратегии и победим. Значит, у первого тоже есть выигрышная стратегия. Противоречие.

Доказали, что первый игрок имеет выигрышную стратегию.

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

Итак, пусть у ноликов есть выигрышная стратегия. Тогда она есть и у крестиков. Рассмотрим следующую стратегию для крестиков. Первый ход делается карандашом и как бы не замечается в дальнейшем. Условно говоря, крестики смотрят на позицию через очки, в которых карандашный крестик не виден, а видны только следующие («чернильные») и применяют стратегию для ноликов (только вместо крестиков ставятся нолики и наоборот; можно сказать, что через очки чернильные крестики видны как нолики, а нолики — как крестики).

Подробно докажем корректность такой стратегии. Во-первых, стратегия может предписывать поставить чернильный крестик на место карандашного, но правилами игры требуется на каждом шаге ставить новый крестик. Тогда мы должны обвести карандашный крестик чернилами, но взамен на свободном месте поставить новый карандашный крестик. Тогда все правила игры (и основной, и имитируемой игры за второго игрока) будут соблюдены.

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

Во-вторых, наличие дополнительного крестика может прервать игру раньше времени — но в этом случае крестики просто выиграют раньше.

Так как игра конечна, то один из игроков имеет выигрышную стратегию. Докажем, что второй не может иметь выигрышной стратегии. Предположим, что она у него есть, и будем играть за первого. Первым ходом напишем число 1. Второй игрок своим ходом напишет какое-то однозначное число (большее 1). С этого момента у второго игрока есть ответные ходы на каждый наш ход, соответствующие выигрышной стратегии. Тогда можем начать игру по-другому: первым ходом напишем однозначное число . Теперь будем отвечать на ходы второго по его же стратегии и победим, так как игра в первом случае и во втором абсолютно одинаковая (первая единица в первом случае не влияет на дальнейшую игру), а игроки, совершающие ход после выписанного числа — разные. Значит, у первого тоже есть выигрышная стратегия. Противоречие.

Доказали, что первый игрок имеет выигрышную стратегию.