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

Доказательство. Проводим индукцию по максимальному числу
оставшихся ходов в позиции (𝑃, 𝑄). Обозначая оценку буквой 𝜑, дока-
зываемое равенство можно записать как
𝜑(𝑃, 𝑄) = 𝜑(𝑃) ⊕ 𝜑(𝑄).
По определению мы должны проверить, что
• 𝜑(𝑃) ⊕ 𝜑(𝑄) отличается от 𝜑(𝑃
′
, 𝑄
′
) для любой позиции (𝑃
′
, 𝑄
′
), в
которую можно пойти из (𝑃, 𝑄);
• 𝜑(𝑃) ⊕ 𝜑(𝑄) является наименьшим числом с таким свойством.
По определению суммы игр один из членов пары (𝑃
′
, 𝑄
′
) остался тем же,
что в паре (𝑃, 𝑄), а другой получился ходом в игре-слагаемом. Поэтому
величина 𝜑(𝑃
′
, 𝑄
′
), по предположению индукции равная 𝜑(𝑃
′
) ⊕ 𝜑(𝑄
′
),
отличается от 𝜑(𝑃)⊕𝜑(𝑄) ровно в одном слагаемом, и остаётся воспользо-
ваться первыми двумя свойствами операции ⊕. Первая часть доказана.
Чтобы доказать вторую, рассмотрим произвольное целое неотрица-
тельное 𝑘, меньшее 𝜑(𝑃) ⊕ 𝜑(𝑄). По третьему свойству операции ⊕ число
𝑘 можно представить в виде 𝑝
′
⊕ 𝜑(𝑄) с 𝑝
′
< 𝜑(𝑃) или в виде 𝜑(𝑃) ⊕ 𝑞
′
с
𝑞
′
< 𝜑(𝑄). Пусть верно, скажем, первое. Тогда (по определению оценки)
𝑝
′
равно 𝜑(𝑃
′
) для некоторой позиции 𝑃
′
, в которую можно пойти из 𝑃, и
потому
𝑘 = 𝑝
′
⊕ 𝜑(𝑄) = 𝜑(𝑃
′
) ⊕ 𝜑(𝑄) = 𝜑(𝑃
′
, 𝑄)
(последнее равенство верно по предположению индукции), так что 𝑘
встречается среди оценок позиций, в которые можно пойти из (𝑃, 𝑄).
Теорема доказана.
40

---

(Заметим, что в доказательстве мы использовали не определение опе-
рации ⊕ как поразрядного сложения, а её индуктивное определение.)
Пример. Игра «ним» с двумя кучками спичек представляет собой
сумму двух игр с одной кучкой. Поэтому оценка позиции (𝑚, 𝑛) (в одной
кучке 𝑚 спичек, в другой 𝑛) равна побитовой сумме оценок позиций 𝑚
и 𝑛 в игре с одной кучкой, то есть 𝑚 ⊕ 𝑛. В частности, позиция (𝑚, 𝑛)
является проигрышной, если 𝑚 ⊕ 𝑛 = 0, то есть 𝑚 = 𝑛.
Аналогично можно разобрать и игру с тремя кучками (которая есть
сумма игры с двумя кучками и игры с одной кучкой). Получится, что
оценка позиции (𝑚, 𝑛, 𝑘) равна 𝑚 ⊕ 𝑛 ⊕ 𝑘. (Заметим, что операция ⊕ ассо-
циативна, то есть (𝑚⊕𝑛)⊕𝑘 равно 𝑚⊕(𝑛⊕𝑘), что следует, например, из
её определения как поразрядного сложения. Поэтому можно записывать
𝑚 ⊕ 𝑛 ⊕ 𝑘 без скобок.)
Таким образом, проигрышными являются позиции, когда 𝑚⊕𝑛⊕𝑘 =
0, то есть те позиции, для которых в каждом разряде сумма по модулю 2
равна нулю (стоит чётное число единиц). Таким образом, мы передока-
зали результат раздела 4.
Отметим ещё такое