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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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