Однажды Сильвер предложил такую игру: есть несколько кучек монет, два игрока по-очереди берут монеты из любой кучки --- но только из одной. Брать можно не меньше одной монеты, но хоть всю кучку. Кто взял последнюю монету --- выиграл. В другом варианте --- кто взял последнюю, тот проиграл.
Игра известна как "игра Ним" и обычно описывается для кучек спичек. Если подумать, видна связь с разламыванием плитки (табака или, скажем, шоколада). Если выигрывает тот, кто забрал последнюю монету, то решением является инвариант на базе поразрядной суммы в двоичном разложении.
А вы спрашивали, где нужна двоичная система, кроме информатики!
Для двух кучек все просто: надо держать их равными, по числу монет. Противник возьмет из одной кучки сколько угодно --- Сильвер возьмет из другой столько же. Все кончится либо ситуацией 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.
Вот такая любопытная игра! В ней применяется нестандартная алгебраическая операция и "чисто компьютерная" двоичная система. Подписывайтесь, будет еще много интересного!