ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 115393
Темы:    [ Выигрышные и проигрышные позиции ]
[ Разбиения на пары и группы; биекции ]
Сложность: 4-
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Два игрока ходят по очереди. Перед началом игры у них есть поровну горошин. Ход состоит в передаче сопернику любого числа горошин. Не разрешается передавать такое количество горошин, которое до этого уже кто-то в этой партии передавал. Ноль горошин тоже передавать нельзя. Тот, кто не может сделать очередной ход по правилам, — считается проигравшим.
Кто — начинающий или его соперник — победит в этой игре, как бы ни играл его партнёр?
Рассмотрите случаи:
а) У каждого по две горошины;
б) У каждого по три горошины;
в) У каждого по десять горошин;
г) Общий случай: у каждого по N горошин.

Решение

Во всех случаях победит второй игрок.
В пункте "а", когда у игроков по две горошины, первый игрок либо отдаст второму две горошины (на это второй даст ему одну, и у первого не будет ходов), либо отдаст одну. В этом случае второй игрок может отдать ему две горошины, назад получит три, отдаст четыре и победит.
Подобным же образом пойдёт игра и в пункте "б". Если первый игрок отдаст три или две, назад получит одну и сразу проиграет. Если же отдаст одну, то назад получит две. Далее у первого два варианта хода, но оба плохи: отдав 4, он получит назад 3 и проиграет, а отдав 3, получит 4, будет вынужден отдать 5, получит 6 и всё равно проиграет.
Разбирать случай 10 горошин, как предлагается в пункте "в", нет смысла. Этот пункт давался для того, чтобы на большом числе горошин почувствовать общую стратегию. Изложим её — это будет решение пункта "г".
г) Первое решение. Победит второй игрок, придерживаясь правила: "всякий раз отдавай минимально возможное число горошин". Докажем, что это действительно стратегия. Достаточно показать, что у второго игрока всегда будет ход. Начинает игру у нас первый игрок, но мы схитрим и сделаем так, чтобы игру начинал второй: предположим, что второй (условно) передаёт сначала первому 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 парных ходов, то есть после окончания игры. Во время же игры такой ситуации сложиться не может. Значит, второй всегда ответит первому и в конце концов победит.

Источники и прецеденты использования

олимпиада
Название Турнир им.Ломоносова
номер/год
Название конкурс по математическим играм
Год 2009
задача
Номер 1

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .