Запас хода

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

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

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

Пронумеруем столбцы слева направо, и строчки сверху вниз. Будем обозначать через клетку на пересечении -ого столбца и -ой строчки. Играем за первого игрока. Сначала сходим в клетку . Теперь, если второй игрок не сходит в клетку , то мы сможем сходить в одну из клеток или и тем самым заблокировать для второго игрока клетку . Тогда далее будем играть произвольно, не ходя в клетку . Если мы в какой-то момент не можем сделать ход, то и второй игрок не может сделать хода. Тогда нам достаточно сходить в клетку . Значит, первым своим ходом второй игрок ходит в . Тогда сходим далее в клетку . Легко видеть, что мы создали себе «запас» в виде клетки , в которую мы сможем сходить на любом ходе (второй игрок не может ее заблокировать). То есть снова будем ходить произвольно, пока можем. Если когда-нибудь не сможем, то сходим в и у второго не будет хода.

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

Приведём одну из возможных выигрышных стратегий за Пашу.

Пронумеруем шарики подряд числами от 1 до 2021. Первым ходом покрасим в красный цвет шарик номер 1011 (средний во всём ряду). Пусть Вова, не умаляя общности, свой ход сделал в левую половину. Тогда вторым ходом Паша красит в жёлтый цвет шарик с номером 1014.

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

Осталось заметить, что Паша может заставить Вову сделать ход между покрашенными первыми двумя ходами шариками. Сам Паша туда ходить не будет, и после покраски всех остальных шариков по чётности будет ход Вовы. Значит, Паша победит.

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

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

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

Выигрышная стратегия Чекалинского состоит в том, чтобы каждый раз переворачивать одну и ту же карту (например, пиковую даму). Все возможные позиции можно разбить на пары, отличающиеся лишь расположением пиковой дамы. Если в ответ на ход Чекалинского Германн тоже перевернёт пиковую даму, то повторится предыдущая позиция, и он проиграет. Поэтому он вынужден переворачивать другую карту. А Чекалинский, перевернув в ответ пиковую даму, получит позицию, парную к той, которая только что была. Таким образом, каждым ходом Германну придётся “начинать” новую пару, и Чекалинский всегда сможет сделать ответный ход, “закончив” пару. Так как количество возможных позиций конечно, то рано или поздно Германн не сможет открыть новую пару и проиграет.