Как-то раз Сильвер предложил Билли Бонсу поиграть в игру с плиткой... скажем табака. Плитка поделена на дольки линиями. Игрок ломает плитку по любой линии, но один раз. Кусок оставляет себе, другой отдает противнику. Тот ломает и отдает один кусок. Проигрывает тот, кто получил одну дольку, которую по линии уже не разломить.
Излишне говорить, что выигрывал всегда Сильвер. Когда Бонс понял, в чем дело, Сильвер предложил играть пачками плиток: за ход можно либо разломить каждую плитку в пачке по одной и той же линии, либо снять несколько плиток сверху. Бонс решил, что здесь-то у него будут шансы, но ошибся. Проиграв все запасы, он вызвал Сильвера на дуэль... но это уже другая история.
Как же Сильвер выиграл?
Давайте же вдумчиво и неторопливо разберемся с этой задачкой. Сначала просто нащупаем путь к решению. Рассуждаем с конца. Получить от противника полоску шириной в одну дольку --- это победа, ведь достаточно отломить одну дольку и вернуть ее противнику.
Но как заставить противника прислать полоску шириной в одну дольку? Он же тоже понимает, что это его проигрыш! Если хоть по одной стороне есть хотя бы три дольки, он не будет этого делать, не так ли? Значит, надо дать ему квадрат 2х2 дольки! Получается, что полоса 2хn долек, при n>2 --- это победа: мы отломим 2х2, получим 2х1 и победим. Но как заставить противника дать нам такую полоску? Только 3х3... По индукции получается, что надо давать противнику квадрат (считая ширины сторон в дольках!). Если изначально плитка не квадратная, надо ходить первым, а если квадратная --- то вторым.
Теперь возьмем полученное решение и докажем, что оно верное. Получивший квадрат Билли победить сразу не может --- это очевидно. При этом он неизбежно испортит квадрат, сделав разлом. Но противник "квадратность" восстановит, с уменьшением размера. В итоге квадрат неизбежно уменьшится до 1х1, то есть до одной дольки, которую и получит незадачливый Билли.
Для трех измерений нам нужно что-то другое. Пачка плиток описывается тремя числами: размерами плиток N и M (они все одинаковые) и количеством K плиток в пачках (они тоже все одинаковые). Равенство всех трех характеристик пачки Сильвер за один ход обеспечить не может. Ему нужен какой-то параметр I(N,M,K), зависящий от этих трех чисел, такой, что:
- Для одной дольки он равен нулю: I(1,1,1)=0;
- Сильвер всегда может сделать его равным нулю, уменьшив одно число/
- Бонс, получив пачку с нулевым параметром, не может оставить его равным нулю (изменив только одно число).
Такие величины --- инварианты --- находить трудно. В данном случае природа инварианта --- двоичная.
Запишем числа в двоичной системе: представим в виде суммы степеней двойки. Алгоритм простой: делим с остатком на два --- получаем двоичную цифру; делим нацело на два; повторяем, пока число не превратится в нуль.
Например, 5 выглядит как 101, а 7 --- как 111. Отметим, что число всегда можно дополнить слева нулями, поэтому числа можно считать состоящими из одного и того же количества цифр.
Определим такую операцию, как поразрядную сумму. Она проводится по-отдельности с каждой цифрой по таким правилам: 0+0=0, 0+1=1, 1+0=1, 1+1=0. Записав три числа друг под другом, мы можем вычислить поразрядную сумму всех трех, получив новое число.
Например, пусть плитки 5 на 7 долек и в пачке 9 плиток:
0101
0111
1001
Поразрядная сумма, справа налево: 1+1+1=1, 0+1+0=1, 1+1+0=0, 0+0+1=1. В итоге, имеем 1011 --- это число 11.
Вот такая поразрядная сумма --- это и есть искомый инвариант! Но не от самих чисел N, M, K, а от N-1, M-1, K-1. В самом деле, для N=M=K=1 он равен нулю. Если он равен нулю, то Бонс, уменьшая одно число, неизбежно заменит хотя бы одну единичку на нолик --- в этом разряде поразрядная сумма станет равна единице, а значит, и весь инвариант уже не нуль. Наконец, получив ненулевое I, Сильвер может изменить одно число так, чтобы восстановить нулевое значение инварианта.
Возьмем наш пример: N=5, M=7, K=9:
0100 + 0110 + 1000 = 1010 (+ обозначает поразрядную сумму). Если Сильвер снимет одну пачку, сумма станет 0101; если еще одну, то 0100; и еще четыре: 0000. Желанный ноль получен! Сильверу надо снять из пачки 6 плиток.
Что делает Бонс --- не важно. Допустим, он отломит по полоске в одну дольку с каждой плитки, передав Сильверу 4x7x3, то есть I=011+110+010=111.
А Сильвер отломит с другого края четыре (100 в двоичном коде) и еще одну (всего пять), превратив 7 в 2, то есть заменив 110 (это 7-1=6) на 001: I=011+001+010=000.
И так далее! В конце концов игра станет двумерной --- перейдет к одной плитке или к стопке плиток шириной в одну дольку, а алгоритм --- в предыдущий: число K=1 даст слагаемое из одних нулей, и двоичные цифры двух других слагаемых должны просто совпадать.
Двоичная природа игры остается таковой для любой размерности. У пиратов пачки плиток могли быть уложены в коробки слоями, а коробки --- в ящики, тоже слоями. Принцип тот же, только слагаемых в поразряной сумме больше. И играть как-то неудобно...
Есть игра Ним, полностью эквивалентная нашей --- о ней в следующей заметке.