Два игрока ходят по очереди. Перед началом игры у них есть поровну горошин. Ход состоит в передаче сопернику любого числа горошин. Не разрешается передавать такое количество горошин, которое до этого уже кто-то в этой партии передавал. Ноль горошин тоже передавать нельзя. Тот, кто не может сделать очередной ход по правилам, считается проигравшим. Кто — начинающий или его соперник — победит в этой игре, как бы ни играл его партнёр?
Рассмотрите случаи:
а) У каждого по две горошины;
б) У каждого по три горошины;
в) Общий случай: у каждого по N горошин.
Задача была предложена на конкурсе по математическим играм Турнира имени Ломоносова в 2009 году.
Во всех случаях победит второй игрок.
В пункте «а», когда у игроков по две горошины, первый игрок либо отдаст второму две горошины (на это второй даст ему одну, и у первого не будет ходов), либо отдаст одну. В этом случае второй игрок может отдать ему две горошины, назад получит три, отдаст четыре и победит.
Аналогично пойдёт игра и в пункте «б». Если первый игрок отдаст три или две, назад получит одну и сразу проиграет. Если же отдаст одну, то назад получит две. Далее у первого два варианта хода, но оба плохи: отдав 4, он получит назад 3 и проиграет, а отдав 3, получит 4, будет вынужден отдать 5, получит 6 и всё равно проиграет.
Первое решение пункта в). Победит второй игрок, придерживаясь правила: «всякий раз отдавай минимально возможное число горошин». Докажем, что это действительно стратегия. Достаточно показать, что у второго игрока всегда будет ход. Начинает игру у нас первый игрок, но мы схитрим и сделаем так, чтобы игру начинал второй: предположим, что второй (условно) передаёт сначала первому 0 горошин. Теперь можно видеть, что всякий раз в ответ на ход второго первый игрок вынужден будет отдать ему больше, чем сам получил. Поэтому количество горошин у второго с каждым парным ходом будет увеличиваться хотя бы на одну. Перед K-м ходом у него будет не менее N+K горошин. А отдать на K-м ходу он в соответствии со своей стратегией должен не более 2K горошин. Это осуществимо, поскольку N+K>=2K при K<=N. А более, чем N ходов игра длиться не может.
Второе решение пункта в). Разобьём числа от 1 до 2N на пары
(1 ; 2), (3 ; 4), (5 ; 6)
и так далее. Победит второй игрок, придерживаясь правила: «всякий раз, получив число из некоторой пары, отдавай другое число из той же пары». Докажем, что и это верная стратегия. Опять же, требуется показать, что у второго игрока всегда будет ход. Пусть первый передал второму число x из некоторой пары (x;y). Ясно, что y никто пока не передавал: второй это мог делать только в ответ на ход первого x, а если бы первый ранее передал бы y, то второй тогда же передал бы x. Что же может помешать второму отдать y? Только отсутствие у него нужного количества горошин. Однако, поскольку y>=x+1, а x он только что получил, отдать y второй не сможет только в одном случае: если у него ничего до хода первого не было. Но за каждый парный ход у первого количество горошин может уменьшиться максимум на одну, а было у него N, так что 0 у него может быть только после N парных ходов, то есть после окончания игры. Во время же игры такой ситуации сложиться не может. Значит, второй всегда ответит первому и в конце концов победит.
