Number Duel 数学
NimゲームとSprague-Grundyの定理
シンプルなゲームを想像してください。テーブルの上に石の山がいくつかあります。2人のプレイヤーが交互に石を取ります。各ターンで、1つの山を選んで任意の数の石を取ります（少なくとも1つ）。最後の石を取ったプレイヤーの勝ちです。
これがNimです。数学において最も重要なゲームの一つなのは、人が楽しむためというより、Nimを理解することで戦略ゲームの全家族を解くための道具が得られるからです。
基本的なゲーム
具体例から始めましょう。3つの山にそれぞれ3、4、5個の石があります。
山A: ●●●
山B: ●●●●
山C: ●●●●●
あなたが先手です。勝つ手は？直感では役に立ちません——答えには2進数の計算が必要です。
2進数のトリック
Charles Boutonは1901年にNimには完全な解があることを証明しました。鍵はnim和です。すべての山の大きさのXOR（排他的論理和）を2進数で計算します。
例（3、4、5の山）：
3 = 0 1 1
4 = 1 0 0
5 = 1 0 1
XOR ---------
0 1 0 = 2
Boutonの定理：
- nim和が0 → その局面は負け（次に指す人が最善の相手には負ける）
- nim和が0以外 → その局面は勝ち（次に指す人が必勝手を持つ）
nim和が2なので先手必勝です。必勝手は、nim和が0になるように石を取ることです。
山C（5個）から2個取ると（5→3）、新しいnim和：
011 ⊕ 100 ⊕ 011 = 000 ✓
その後、相手が何をしても、nim和を0に戻す手が必ずあります。
なぜXORなのか
XORが機能する理由は自己逆元性にあります：a ⊕ a = 0。nim和が0の局面では、すべての山が2進数で「ペアリング」されています。相手がペアを壊せば、あなたがペアを戻します。相手が別のペアを壊せば、あなたがそれを戻します。常に応手があります。
Nimの変種
Bashゲーム（バシェのゲーム）
N個の石の1つの山。毎回1〜K個取れる。Nが(K+1)の倍数なら後手必勝、それ以外は先手必勝。
Wythoffのゲーム
2つの山。1つの山から任意の数、または両方から同じ数取れる。負けの局面が黄金比φ = (1+√5)/2に関連する驚くべきパターンを形成します。
(1, 2), (3, 5), (4, 7), (6, 10), (8, 13)...
各ペアは ⌊nφ⌋ と ⌊nφ²⌋ です。これらはBeatty数列と呼ばれ、黄金比が最も無理数らしい数であるために、数列が重ならず隙間なく覆います。
Sprague-Grundyの定理
ここが画期的な部分です。1935年、Roland SpragueとPatrick Grundyが独立に証明しました：すべての公平な2人ゲームはNimの山と等価である。
「公平」とは両プレイヤーが同じ手を選べるゲームです。等価とは、ゲームが特定のサイズのNimの山と同じ勝敗構造を持つことです。
各局面にGrundy数を割り当てます：
- 次の局面がない → Grundy数 = 0
- それ以外 → Grundy数 = mex（到達可能なGrundy数の集合に含まれない最小の非負整数）
複数の独立したサブゲームからなるゲームでは、全体のGrundy数 = 各サブゲームのGrundy数のXOR。Nimそのものと同じです。
Number Duelとの関係
Number Duelのゲームは純粋な公平ゲームではありませんが、同じ考え方が適用できます。
- Sum Duelでは、各手が利用可能なマスと相手の選択肢を変えます。Nimと同じく、相手に「負けの局面」を残すことが目標です。
- Fifteen Duelはマルバツゲームと等価で、完全に解かれています。
Sprague-undyの定理はこの種の分析の理論的基盤です。ゲームがいくら複雑に見えても、その下には常にNimのような構造が隠れています。