✅ Его первый ход выглядит почти случайным: он убирает 2 камня из кучки с 7 камнями. После этого на столе лежат две равные кучки — 5 и 5.
А дальше игра превращается в зеркальный «танец». Что бы ни сделал второй игрок — скажем, уберёт 3 камня из одной кучки, — первый тут же убирает 3 камня из другой. Если второй возьмёт 1 камень, первый берёт 1 из противоположной кучки. Если второй решит забрать сразу всё, первый делает то же самое со второй кучкой. Симметрия больше не нарушается, а значит, последним ходит тот, кто эту симметрию создал, — первый игрок.
Заметьте, что ключевой момент не в количестве камней — «2», — а в создании равенства. Очевидно, что если бы кучки были, например, по 2025 и 2026 камней или ещё больше, то решение не поменялось бы.
Позиции вида (5,5), (100,100), (2025,2025) — проигрышные для того, кто ходит. Любой ход разрушает симметрию, и соперник может её восстановить. Поэтому правильная стратегия формулируется лаконично: нужно перевести игру в проигрышную позицию для соперника.
В случае двух кучек всё выглядит почти тривиально: проигрышные позиции — это просто равные числа. Но стоит добавить третью кучку — и зеркало ломается. Как зеркалить три разных числа? Что делать с позицией (1,2,3)? Или (4,7,10)?
Тут начинается «взрослая» математика!
Секрет скрывается не в симметрии как таковой, а в двоичной записи чисел. Нужно сложить размеры кучек «без переноса» — поби́тово, по модулю два. Эта операция называется XOR. Если результат равен нулю, позиция проигрышная. Если нет — выигрышная.
Для двух кучек это правило говорит ровно то, что мы уже увидели: a XOR b равно нулю тогда и только тогда, когда a = b. Наша «зеркальная стратегия» оказывается частным случаем куда более общей арифметики.
🔄Так простая игра с камнями неожиданно приводит к бинарной системе счисления, к алгебре без переноса и к целой теории комбинаторных игр. В начале XX века Чарльз Бутон полностью описал стратегию для игр Ним.
Это общее название игр, в которых два игрока по очереди берут предметы, разложенные на несколько кучек, и за один ход можно взять любое количество предметов (больше нуля) из одной кучки. В классическом варианте число кучек равно трём.
Позже на её основе появилась теорема Шпрага-Гранди — фундамент современной теории игр такого типа🔄
Удивительно, что всё это начинается с почти детского вопроса: «Сколько камешков взять, чтобы точно выиграть?», согласны?
#задача