Ним и ним-сумма

Ним — игра, к которой сводятся все беспристрастные игры, и волшебство ним-суммы (XOR куч).

Ним: несколько куч камней, за ход берут любое положительное число камней из одной кучи; кто не может ходить — проиграл. Позиция проигрышна тогда и только тогда, когда XOR размеров всех куч равен нулю.

Зачем это в олимпиадах

Ним — центральная игра всей теории: по теореме Шпрага–Гранди (следующий урок) любая беспристрастная игра эквивалентна ниму с одной кучей. Поэтому понять ним — значит получить ключ ко всему классу игровых задач. А критерий выигрыша поражает простотой: достаточно посчитать XOR (ним-сумму) размеров куч. XOR-трюки вообще пронизывают олимпиадную математику, и ним — самый яркий пример, где XOR появляется «из ниоткуда» и идеально решает задачу.

Ним с одной кучей и с двумя равными

Начнём с интуиции. Одна куча: первый игрок забирает её целиком и выигрывает — позиция всегда выигрышна (кроме пустой). Две равные кучи: первый игрок в проигрыше! Что бы он ни взял из одной кучи, второй повторяет ход в другой, восстанавливая равенство. Рано или поздно первый окажется перед двумя пустыми кучами и проиграет. Стратегия «зеркало» подсказывает: важна не сумма, а некий баланс между кучами. Этим балансом оказывается XOR.

Критерий нима: ним-сумма

Теорема Бутона: позиция нима с кучами a₁, a₂, …, aₙ проигрышна (для того, чей ход) тогда и только тогда, когда ним-сумма a₁ ⊕ a₂ ⊕ … ⊕ aₙ = 0.

Здесь ⊕ — побитовый XOR. Две равные кучи дают a ⊕ a = 0 — проигрыш, что согласуется с интуицией «зеркала». Проверим теорему перебором: сравним честную разметку W/L (через рекурсию из прошлого урока) с критерием XOR.

from functools import reduce
from itertools import product

def nim_xor(piles):
    return reduce(lambda a, b: a ^ b, piles, 0)

# Честная разметка для проверки (медленная, для маленьких куч)
def is_losing(piles, memo={}):
    key = tuple(sorted(piles))
    if key in memo:
        return memo[key]
    # перебираем все ходы
    for i, p in enumerate(piles):
        for take in range(1, p + 1):
            nxt = list(piles)
            nxt[i] -= take
            if is_losing(nxt):           # есть ход в проигрышную -> текущая выигрышна
                memo[key] = False
                return False
    memo[key] = True                     # все ходы в выигрышные -> проигрышна
    return True

# Сверяем критерий XOR с честной разметкой для всех куч до 4 камней
ok = True
for a, b, c in product(range(5), repeat=3):
    if is_losing([a, b, c]) != (nim_xor([a, b, c]) == 0):
        ok = False
print("Критерий XOR совпал с разметкой:", ok)
print("XOR(3,4,5) =", nim_xor([3, 4, 5]), "->", "проигрыш" if nim_xor([3,4,5])==0 else "выигрыш")

Вывод:

Критерий XOR совпал с разметкой: True
XOR(3,4,5) = 2 -> выигрыш

Перебор подтвердил: проигрышные позиции — ровно те, где ним-сумма ноль. Для куч (3,4,5) XOR равен 2 (не ноль) — позиция выигрышная, у первого игрока есть победный ход.

Почему XOR? Интуиция и доказательство

Доказательство опирается на два свойства. Из позиции с XOR = 0 любой ход делает XOR ≠ 0. Действительно, изменив одну кучу, мы меняем её вклад в XOR, и сумма перестаёт обнуляться (нельзя изменить число, не изменив XOR). Из позиции с XOR ≠ 0 есть ход в позицию с XOR = 0. Пусть x = ним-сумма, d — её старший единичный бит. Найдётся куча aᵢ, у которой бит d тоже единичный (иначе он не появился бы в XOR). Уменьшим её до aᵢ ⊕ x — это меньше aᵢ (старший бит гасится), и новая ним-сумма станет нулём. Терминальная позиция (все кучи пусты) имеет XOR = 0 и проигрышна — база совпадает. Значит XOR = 0 ⟺ проигрыш.

Поиск выигрышного хода

Критерий не только говорит, кто выиграет, но и подсказывает как: найти кучу с установленным старшим битом ним-суммы и уменьшить её до aᵢ ⊕ x.

from functools import reduce

def winning_move(piles):
    x = reduce(lambda a, b: a ^ b, piles, 0)
    if x == 0:
        return None                  # проигрышная позиция, хода нет
    for i, a in enumerate(piles):
        target = a ^ x
        if target < a:               # эту кучу можно уменьшить до target
            return i, a - target     # индекс кучи и сколько взять
    return None

piles = [3, 4, 5]
move = winning_move(piles)
print(move)                          # из какой кучи и сколько взять
i, take = move
piles[i] -= take
print(piles, reduce(lambda a, b: a ^ b, piles, 0))  # новая ним-сумма = 0

Вывод:

(0, 2)

Вывод (продолжение):

[1, 4, 5] 0

Алгоритм велит взять 2 камня из кучи 0: 3 → 1. Новая позиция (1,4,5) имеет ним-сумму 1⊕4⊕5 = 0 — теперь в проигрыше соперник. Дальше, какой бы ход он ни сделал, мы снова сможем обнулить ним-сумму — и так до победы.

Разбор задачи: ним с ограничением на ход

Частая олимпиадная вариация — «ним по модулю»: из кучи можно брать не больше m камней за раз. Кажется, что критерий XOR ломается, и отчасти так и есть: теперь значение Гранди одной кучи равно не её размеру, а n mod (m+1). Но структура сохраняется: значение Гранди составной игры — XOR значений Гранди куч. Это мостик к следующему уроку: ним перестаёт быть «эталоном напрямую», зато общая теория Шпрага–Гранди продолжает работать.

from functools import reduce

def grundy_limited(n, m):
    return n % (m + 1)            # из кучи берут 1..m камней

# Три кучи 7, 8, 9; за ход берут не больше 3 камней.
piles = [7, 8, 9]
m = 3
g = [grundy_limited(p, m) for p in piles]
total = reduce(lambda a, b: a ^ b, g, 0)
print(g, "-> XOR =", total)
print("Первый игрок:", "выигрывает" if total else "проигрывает")

Вывод:

[3, 0, 1] -> XOR = 2

Вывод (продолжение):

Первый игрок: выигрывает

Значения Гранди куч — 7 mod 4 = 3, 8 mod 4 = 0, 9 mod 4 = 1; их XOR равен 2 — позиция выигрышная. Обратите внимание: обычный ним — это частный случай при m = ∞ (нет ограничения), и тогда n mod (m+1) = n возвращает классический критерий. Так одна формула покрывает целое семейство игр, а XOR-сложение Гранди остаётся универсальным.

Подводные камни

• XOR, а не сумма. Частая ошибка — считать обычную сумму куч. Работает именно побитовый XOR.
• Нормальное соглашение. Критерий XOR=0 для проигрыша верен при «кто не может ходить — проиграл». В мизер-ниме правило чуть иное (отличается в позициях из единичных куч).
• XOR в Python. Оператор ^, не ** и не xor. Для списка удобно reduce(lambda a,b:a^b, piles).
• Пустые кучи. Куча размера 0 не мешает: её вклад в XOR — ноль.

Итог

• Ним: берут любое число камней из одной кучи; теорема Бутона — проигрыш ⟺ XOR куч = 0.
• Из XOR=0 любой ход уводит в XOR≠0; из XOR≠0 есть ход в XOR=0 (через старший бит).
• Выигрышный ход: уменьшить кучу aᵢ до aᵢ ⊕ x, где x — ним-сумма.
• Ним — модель, к которой сводятся все беспристрастные игры (следующий урок).