Задание №177519: Турнир Ломоносова 2009

1. «Горошины». Во всех случаях победит второй игрок.
В пункте «а», когда у игроков по две горошины, первый игрок либо
отдаст второму две горошины (на это второй даст ему одну, и у первого
не будет ходов), либо отдаст одну. В этом случае второй игрок может
отдать ему две горошины, назад получит три, отдаст четыре и победит.
Подобным же образом пойдёт игра и в пункте «б». Если первый
игрок отдаст три или две, назад получит одну и сразу проиграет. Если
же отдаст одну, то назад получит две. Далее у первого два варианта
хода, но оба плохи: отдав 4, он получит назад 3 и проиграет, а отдав 3,
получит 4, будет вынужден отдать 5, получит 6 и всё равно проиграет.
Разбирать случай 10 горошин, как предлагается в пункте «в», нет
смысла. Этот пункт давался для того, чтобы на большом числе горо
шин почувствовать общую стратегию. Изложим её — это будет решение
пункта «г».
г) Первое решение. Победит второй игрок, придерживаясь правила:
«всякий раз отдавай минимально возможное число горошин». Докажем,
что это действительно стратегия. Достаточно показать, что у второго
игрока всегда будет ход. Начинает игру у нас первый игрок, но мы
схитрим и сделаем так, чтобы игру начинал второй: предположим, что
второй (условно) передаёт сначала первому 0 горошин. Теперь можно
видеть, что всякий раз в ответ на ход второго первый игрок вынуж
ден будет отдать ему больше, чем сам получил. Поэтому количество
горошин у второго с каждым парным ходом будет увеличиваться хотя
бы на одну. Перед 𝐾-м ходом у него будет не менее 𝑁 + 𝐾 горошин.
А отдать на 𝐾-м ходу он в соответствии со своей стратегией должен
не более 2𝐾 горошин. Это осуществимо, поскольку 𝑁 + 𝐾 (cid:62) 2𝐾 при
𝐾 (cid:54) 𝑁. А более, чем 𝑁 ходов игра длиться не может.


32

Второе решение. Разобьём числа от 1 до 2𝑁 на пары
(1; 2), (3; 4), (5; 6)

и так далее. Победит второй игрок, придерживаясь правила: «всякий
раз, получив число из некоторой пары, отдавай другое число из той
же пары». Докажем, что и это верная стратегия. Опять же, требуется
показать, что у второго игрока всегда будет ход. Пусть первый пере
дал второму число 𝑥 из некоторой пары (𝑥; 𝑦). Ясно, что 𝑦 никто пока
не передавал: второй это мог делать только в ответ на ход первого 𝑥,
а если бы первый ранее передал бы 𝑦, то второй тогда же передал бы 𝑥.
Итак, что же может помешать второму отдать 𝑦? Только отсутствие у
него нужного количества горошин. Однако, поскольку 𝑦 (cid:62) 𝑥 + 1, а 𝑥 он
только что получил, отдать 𝑦 второй не сможет только в одном случае —
если у него ничего до хода первого не было. Однако, за каждый пар
ный ход у первого количество горошин может уменьшиться максимум
на одну, а было у него 𝑁, так что 0 у него может быть только после 𝑁
парных ходов, то есть после окончания игры. Во время же игры такой
ситуации сложиться не может. Значит, второй всегда ответит первому
и в конце концов победит.