Игры и стратегии с точки зрения математики

Лемма 2. (а) Если 𝑚
′
≠ 𝑚, то 𝑚 ⊕ 𝑛 ≠ 𝑚
′
⊕ 𝑛 для любого 𝑛.
(б) Если 𝑛
′
≠ 𝑛, то 𝑚 ⊕ 𝑛 ≠ 𝑚 ⊕ 𝑛
′
при любом 𝑚.
(в) Если 𝑘 < 𝑚⊕𝑛, то 𝑘 = 𝑚
′
⊕𝑛 для некоторого 𝑚
′
< 𝑚 или 𝑘 = 𝑚⊕𝑛
′
для некоторого 𝑛
′
< 𝑛.
Доказательство. Если в сумме 𝑚 ⊕ 𝑛 изменить одно слагаемое, то
оно изменится в некотором разряде — и поразрядная сумма изменится
в том же разряде. Отсюда следуют пункты (а) и (б).
Докажем теперь (в). Пусть 𝑘 < 𝑚 ⊕ 𝑛. Рассмотрим самый старший
разряд, в котором 𝑘 отличается от 𝑚 ⊕ 𝑛. В этом разряде в 𝑘 стоит нуль,
а в 𝑚 ⊕ 𝑛 стоит единица. Значит, (ровно) в одном из чисел 𝑚 и 𝑛 в этом
разряде стоит единица. При замене этой единицы на нуль число умень-
шится, даже если мы изменим младшие разряды так, чтобы подогнать
𝑚 ⊕ 𝑛 к 𝑘. Лемма доказана.
Теперь определим понятие суммы двух игр Шпрага – Гранди. (При
этом суммой двух игр с одной кучкой спичек окажется игра с двумя куч-
39

---

ками спичек.) Неформально говоря, две игры происходят параллельно
(каждая на своей доске), причём игрок может выбрать, на какой из двух
досок он хочет в данный момент ходить. Формально говоря, позиция в
игре-сумме представляет собой пару (𝑃, 𝑄), где 𝑃 — позиция в первой иг-
ре, а 𝑄 — во второй. Из позиции (𝑃, 𝑄) можно пойти в позицию (𝑃
′
, 𝑄)
для любой позиции 𝑃
′
, в которую можно пойти из 𝑃, а также в позицию
(𝑃, 𝑄
′
) для любой позиции 𝑄
′
, в которую можно пойти из 𝑄.
Теорема Шпрага – Гранди. Оценка позиции (𝑃, 𝑄) в сумме двух игр
равна побитовой сумме оценок позиций 𝑃 и 𝑄.
Другими словами, если позиция 𝑃 в первой игре имеет оценку 𝑝, а
позиция 𝑄 во второй игре имеет оценку 𝑞, то позиция (𝑃, 𝑄) в сумме игр
имеет оценку 𝑝 ⊕ 𝑞.