Сильвер и кучки золотых монет

Однажды Сильвер предложил такую игру: есть несколько кучек монет, два игрока по-очереди берут монеты из любой кучки --- но только из одной. Брать можно не меньше одной монеты, но хоть всю кучку. Кто взял последнюю монету --- выиграл. В другом варианте --- кто взял последнюю, тот проиграл.

Игра известна как "игра Ним" и обычно описывается для кучек спичек. Если подумать, видна связь с разламыванием плитки (табака или, скажем, шоколада). Если выигрывает тот, кто забрал последнюю монету, то решением является инвариант на базе поразрядной суммы в двоичном разложении.

А вы спрашивали, где нужна двоичная система, кроме информатики!

Для двух кучек все просто: надо держать их равными, по числу монет. Противник возьмет из одной кучки сколько угодно --- Сильвер возьмет из другой столько же. Все кончится либо ситуацией 1-1 (по одной монете в кучке --- противник возьмет одну, а Сильвер --- другую), либо Сильвер получит одну кучку, которую и заберет целиком.

Для трех и более кучек (впрочем, для двух тоже) запишем количество монет в двоичной системе, представив в виде степеней двоек. Например, 13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0, то есть 1101 (нолик означает, что 2^1 не входит). Можно добавить нули слева: 001101 --- это то же самое.

Поразрядная сумма --- это сумма цифр в одной и той же позиции по модулю два, то есть по правилам 0+0=0, 0+1=1+0=1, 1+1=0. Если эта сумма не состоит из одних нулей, Сильвер может сделать ее таковой, а противник неизбежно "испортит". На последнем шаге Сильвер оставит одни нули, что и означает "заберет последнюю монету".

Пример. Кучек четыре, в них изначально 11, 12, 10 и 15 монет. Запишем в двоичном коде:

1011

1100

1010

1111

-----

0010

Итак, Сильверу следует изъять единичку из второго разряда, например, взяв 2 монеты из самой большой кучки. Допустим, противник заберет себе всю эту кучку. Тогда кучек стало три (формально нули в четвертой сумму не меняют) и сумма равна 1101. Он возьмет одиннадцать монет из второй кучки, превратив 12 (1100) в 1 (0001) и сумма станет опять нулевой. Ну, пусть противник опять заберет эту кучку, оставив две: в 11 монет и в 10:

1011

1010

----

0001

Сильверу следует взять монетку из первой кучки, сделав опять нуль. Кучки стали равными. Далее все понятно.

И противник никак не может "соскочить" --- выигрывает тот, кто оставляет нулевую поразрядную сумму, а это --- Сильвер.

Теперь обсудим второй вариант игры. Пусть тот, кто взял последнюю монету --- проигрывает.

Любопытно, но стратегия игры практически не меняется: Сильвер продолжает оставлять противнику нулевую поразрядную сумму. Но не до самого конца, а пока на столе не останется одна кучка с более чем одной монетой! "Кучек" из одной монеты может быть много.

Смысл в том, чтобы в этот момент оставить противнику нечетное количество одномонетных кучек. Ту, где монет много, надо либо забрать всю, либо оставить в ней одну монету. Тогда противник сделает число четным --- а мы опять сделаем его нечетным. В итоге его четное число станет два, а наше нечетное --- один: это и есть победа, ведь ему придется взять последнюю монету.

Противник может попробовать избегать оставлять одномонетные кучки. Но выхода у него нет. Если кучек останется две, то он получит, рано или поздно, две по две монеты и либо заберет одну кучку целиком (тогда ему оставим полкучки --- монету), либо возьмет одну монету из кучки (а на следующем ходу --- вторую).

Наконец, обсудим обобщение игры. Когда команде надоело проигрывать, Сильвер предложил разрешить брать монеты из двух кучек. Команда решила было, что уж теперь они Сильвера обыграют; но не получилось.

Природы игры по-прежнему двоичная. Но теперь двоичные числа будем поразрядно складывать не в двоичной системе, а в троичной: по правилам 0+0=0, 0+1=1, 0+2=2, 1+1=2, 1+2=0, 2+2=1 (остаток от деления обычной суммы на три). Сильверу надо присылать противнику нулевую сумму --- это всегда возможно, а противник не может нулевую сумму не испортить.

Если можно брать из N кучек, складывать будем в (N+1)-ичной системе, то есть сумма цифр --- это остаток от деления обычной суммы на N+1.

Вот такая любопытная игра! В ней применяется нестандартная алгебраическая операция и "чисто компьютерная" двоичная система. Подписывайтесь, будет еще много интересного!