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