Nim 和と Nim 積の再帰的な定義

• $a \oplus b = \operatorname{mex}(\{ a' \oplus b \mid 0 \leq a' < a\} \cup \{ a \oplus b' \mid 0 \leq b' < b\} )$
• $a \otimes b = \operatorname{mex}\{ (a' \otimes b) \oplus (a \otimes b') \oplus (a' \otimes b') \mid 0 \leq a' < a,\ 0\leq b' < b\})$

Nim 和・Nim 積の組合せゲーム理論的な説明

• Nim 和: 山2つの Nim
• Nim 積: 2次元 Turning Turtle
  • 不偏ゲーム を参照
  • $(a,b)$ という状態が 1手で $(a', b), (a,b'), (a', b')$ の3つに分裂するイメージ

Nim 和の性質

Nim 和が xor であることは一旦忘れる。

• Nim 和は可換群をなす
  • 結合則: $(a\oplus b ) \oplus c = a \oplus (b\oplus c)$
  • 単位元の存在性: $a \oplus 0 = a$
  • 逆元の存在性: $a\oplus a = 0$
  • 可換則: $a\oplus b = b\oplus a$
• 3つのNim和: 結合則の証明を参照

Nim 積の性質

• $a \otimes 0 = 0$
• Nim和とNim積について体をなす
  • Nim 積は可換モノイドをなす
    • 結合則: $(a\otimes b) \otimes c = a\otimes (b \otimes c )$
    • 単位元の存在 $a \otimes 1 = a$
    • 可換則
  • Nim 和と Nim 積には分配法則が成り立つ: $(a \oplus b) \otimes c = (a\otimes c) \oplus (b \otimes c)$
  • $a \neq 0$ であれば、$a$ には逆元が存在する
• 3つの Nim積: 結合則の証明を参照
• 標数は2
  • $a\oplus a = 0$ なので

Nim 和の計算

• Nim 和は xor
  • 参考: Sprague Grundy Theorem