Задача 158. Игра в «Камешки»-II
На столе лежат
(a) две кучи по 20 камней;
(b) одна куча из 20 камней, другая куча из 30 камней.
Двое игроков играют в следующую игру, делая ходы по очереди. За один ход можно взять любое количество камней, но только из одной кучи. Выигрывает игрок, взявший последний камень. Кто из игроков может выигрывать при правильной игре: начинающий или его соперник?
Решение:
Используем симметричную стратегию: будем поддерживать в кучках равное количество камней. Пусть в первой кучке х камней, а во второй — y, причём x>y. Тогда возьмём из первой (x-y). Теперь в кучках поровну камней. Соперник обязан взять хотя бы один, что нарушит равенство количеств. Ясно, что после хода соперника в обеих кучках не может остаться по 0 камней. Значит, если изначально в кучках поровну камней, то победит второй, иначе — первый.
Ответ:
А) Соперник b) Начинающий.
Задача 158. Игра в «Камешки»-III
Имеются две кучки монет: в первой — 102 монеты, во второй — 99 монет. Андрей и Борис играют в такую игру. За один ход игрок из любой кучки берёт 2 монеты, а затем добавляет 1 монету в другую кучку. Проигрывает тот игрок, который не может сделать ход. Андрей и Борис ходят по очереди. Начинает Андрей. Кто выигрывает при правильной игре?
Подсказка 1
Хм, числа 102 и 99… А может ли первый игрок их уравнять? И если он сделает их равными, то появится ли у него какая-то стратегия?
Подсказка 2
Да, первый игрок может взять две монеты из первой кучи и добавить одну моменту во вторую кучу! То есть, число монет в кучах стало одинаковым. Может ли первый игрок теперь начать отражать ходы второго игрока?
Подсказка 3
Конечно, ведь теперь первый игрок может всегда своим ходом получать кучи с равным количеством монет! То есть, он первым придёт к кучам, в каждой из которых 0 монет!
Решение:
Первым ходом Андрей возьмёт 2 монеты из первой кучи и положит одну во вторую. Тогда после этого хода в кучках будет по 100 монет. Далее Андрей будет действовать симметрично. Заметим, что после каждого хода Андрей в кучках будет равное количество монет, причём количество монет всегда будет уменьшаться на 1. Если после хода Андрея в каждой куче более 1 монеты, то у Андрея будет следующий ход. Тогда игра закончится, когда в кучках будет ровно по 1 камню, причём ход будет за Борисом. Значит, Андрей выиграет.
Ответ:
Андрей
Задача 159. Игра в «Камешки»-IV
В двух кучах лежит по 20 камней. Двое игроков, Андрей и Борис, по очереди берут любое количество камней, но только из одной кучи. Начинает Андрей. Выигрывает тот, кто берет последний камень. Кто из игроков может выиграть, как бы ни играл соперник?
Решение:
Приведем стратегию за Бориса, позволяющую ему победить. Будем играть за Бориса симметрично, то есть брать то же количество камней, что и Андрей, но из другой кучи. Покажем, почему у Бориса всегда есть ход согласно этой стратегии.
Заметим, что после хода Бориса, если он смог сходить, в кучках находится поровну камней, то есть картинка симметрична. Значит, сколько бы камней ни взял Андрей из одной кучи, Борис всегда сможет взять столько же из другой.
Итак, мы доказали, что у Бориса всегда есть ход согласно стратегии. Значит, Борис не может проиграть. Но игра когда-то закончится (например, не позже, чем через 40 ходов, ведь камней в сумме всего 40, а каждым ходом берется хотя бы один камень). Поэтому кто-то все-таки проиграет. Это точно не Борис, поэтому проиграет Андрей.
Ответ:
Борис
Задача 160. Игра в «Камешки»-V
В двух кучах лежат камни: в одной 20 камней, в другой 30. Двое игроков, Андрей и Борис, по очереди берут любое количество камней, но только из одной кучи. Начинает Андрей. Выигрывает тот, кто берет последний камень. Кто из игроков может выиграть, как бы ни играл соперник?
Решение:
Приведем стратегию за Андрея, позволяющую ему победить. Первым ходом возьмем 10 камней из кучи, в которой было 30 камней. Дальше будем играть за Андрея симметрично, то есть брать то же количество камней, что и Борис, но из другой кучи, как это делал Борис в предыдущей задаче.
На самом деле мы получили в точности предыдущую задачу, в которой Андрей и Борис поменялись местами. Поэтому, раз в той игре выигрышная стратегия была у Бориса, то теперь она есть у Андрея. Значит, Андрей может выиграть, как бы ни играл Борис.
Ответ:
Андрей
Задача 161. Игра в «Камешки»-VI
Перед Андреем и Борисом лежат 2020 кучек по одному камушку. За один ход разрешается объединить две кучи с одинаковым числом камней в одну. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре, если начинает Андрей?
Решение:
Заметим, что все кучки в любой момент времени содержат количество камешков равное некоторой степени двойки, так как каждая кучка получается несколькими объединениями (умножениями на два) кучек из 1 камня. Посмотрим на ситуацию, когда кто-то из игроков проигрывает, то есть когда нельзя уже сделать ход. В этот момент 2020 разбилось на несколько различных слагаемых — степеней двоек. Из двоичной системы счисления мы знаем, что любое число единственным образом представляется в виде суммы степеней двоек. Для 2020 это разложение — 1024+512+256+128+64+32+4. То есть в конце всегда остаются эти 7 кучек. Теперь заметим, что за каждый ход количество кучек уменьшается на 1 (две кучки объединяются в одну), то есть из 2020 получится 7 ровно через 2020-7=2013 ходов. Тогда последний ход сделает именно первый, он и победит.
Ответ:
Андрей