Олимпиадная задача по теории алгоритмов и алгебре: игра в горошины для классов 8–11

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

Ответ задачи отсутствует