スプレイグ・グランディの定理と勝ちにつながる手

いくつかの山からなる局面のグランディ数を、各山のグランディ数のニム和として求められる。グランディ数が $0$ の局面へ移る手を、勝ちにつながる手としてすべて数えられる

前提

ニムとニム和（大学数学ゲーム理論）
グランディ数と mex （大学数学ゲーム理論）

この技能までの道筋（9 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
n 進法（数学A 整数の性質）
ニムとニム和（大学数学ゲーム理論）
グランディ数と mex （大学数学ゲーム理論）

説明

山がいくつも並んでいて、1 手で「どれか 1 つの山」にだけ手を加えるゲームを考えます。各山の遊び方がニムと違っていても（取れる個数が限られる、など）、局面全体のグランディ数は各山のグランディ数のニム和として求められます。これがスプレイグ・グランディの定理です。この値が $0$ かどうかで勝敗を判定でき、さらに全体のグランディ数を $0$ にする手、つまり勝ちにつながる手をすべて数え上げられます。

なぜそうしてよいのか

前提として、ゲームは必ず有限手で終わり、最後に手を打った人が勝つ（打てなくなった人が負け）とします。山が $k$ 個ある局面で、各山のグランディ数を $g_{1}, \dots, g_{k}$ とし、 $G = g_{1} \oplus \dots \oplus g_{k}$ とおきます。示したいのは「 $G$ は、1 手で移れる局面のグランディ数の集合の mex に等しい」ということです。これが言えれば、 $G$ がそのまま局面全体のグランディ数になります。終わりに近い局面から順に考える帰納法で、移った先の局面のグランディ数はすでにニム和で表せるとしてよいので、次の 2 点を確かめれば十分です。(a) どの手でも、グランディ数が $G$ の局面へは移れない。(b) $0 \leq t < G$ を満たすどの $t$ についても、グランディ数が $t$ の局面へ移る手がある。

(a) の理由はこうです。1 手では 1 つの山 $i$ だけが変わります。 $g_{i}$ は「山 $i$ から移れる局面のグランディ数に含まれない最小の数」なので、移った先の山のグランディ数 $g_{i}^{'}$ は必ず $g_{i}^{'} \neq = g_{i}$ です。ニム和の中の 1 項だけが別の値に変わるので、全体のニム和も $G$ とは異なる値になります。(b) の理由はこうです。 $d = G \oplus t$ とおきます。 $d$ を 2 進法で表したときに 1 が立っている最上位の桁を考えると、 $t < G$ なのでその桁は $G$ では 1 です。したがって、その桁が 1 である $g_{i}$ が少なくとも 1 つあり、その $g_{i}$ については $g_{i} \oplus d < g_{i}$ となります。mex の定義から、 $g_{i}$ より小さい値はすべて山 $i$ の移り先のグランディ数に現れます。よって山 $i$ をグランディ数 $g_{i} \oplus d$ の状態に変える手があり、移った後の全体のニム和は $G \oplus d = t$ になります。

以上から、局面全体のグランディ数は $G$ です。グランディ数 $0$ の局面は手番の人の負け（後手必勝）で、 $0$ でない局面は手番の人の勝ちです。勝ちにつながる手とは「全体のグランディ数を $0$ にする手」のことで、山 $i$ を、グランディ数が $g_{i} \oplus G$ の状態へ変える手に当たります。ただし、ニムと違って移り先のグランディ数は $g_{i}$ より大きいこともあるので、各山について移り先を実際に表で確かめる必要があります。

手順

1 つの山について、石の数 $n$ ごとのグランディ数 $g (n)$ を mex で小さい順に計算し、表にする（周期があれば見つける）
各山のグランディ数 $g_{1}, \dots, g_{k}$ を表から読み取り、ニム和 $G = g_{1} \oplus \dots \oplus g_{k}$ を 2 進法で計算する
$G = 0$ なら手番の人の負けで、勝ちにつながる手は $0$ 個。 $G \neq = 0$ なら次へ進む
各山 $i$ について目標値 $t_{i} = g_{i} \oplus G$ を求め、山 $i$ から 1 手で移れる状態のうち、グランディ数が $t_{i}$ になるものをすべて数える（移り先が見つからない山もある）
すべての山についての個数を足し合わせ、勝ちにつながる手の総数とする

例題

石の山が 3 つあり、石の数は $2, 5, 6$ 個である。2 人が交互に、どれか 1 つの山から石を $1$ 個、 $2$ 個、 $3$ 個のいずれかの数だけ取る（山にある数より多くは取れない）。最後の石を取った人が勝ちとする。この局面で手番の人が打てる手のうち、勝ちにつながる手（取る山と取る個数の組）の個数を求めよ。

例題の解答

手順 1（1 つの山の表を作る）: $g (0) = 0$ から順に mex を計算すると、 $g (1) = mex {0} = 1$ 、 $g (2) = mex {1, 0} = 2$ 、 $g (3) = mex {2, 1, 0} = 3$ 、 $g (4) = mex {3, 2, 1} = 0$ となる。以降も同じように続き、 $g (n)$ は $n$ を $4$ で割った余りに等しい。 $n = 0, 1, \dots, 7$ に対して $0, 1, 2, 3, 0, 1, 2, 3$ である。

手順 2（ニム和を求める）: 各山のグランディ数は $g (2) = 2$ 、 $g (5) = 1$ 、 $g (6) = 2$ である。2 進法で $10 \oplus 01 \oplus 10 = 01$ なので、 $G = 1$ となる。

手順 3: $G = 1 \neq = 0$ なので、手番の人が勝てる局面である。

手順 4（山ごとに目標値を調べる）:
・2 個の山: 目標値は $t = 2 \oplus 1 = 3$ 。移れるのは 1 個または 0 個の状態で、そのグランディ数は $1, 0$ である。 $3$ はないので、この山には勝ちにつながる手がない。
・5 個の山: 目標値は $t = 1 \oplus 1 = 0$ 。移れるのは 4, 3, 2 個の状態で、グランディ数は $0, 3, 2$ である。 $0$ になるのは 4 個の状態だけなので、「1 個取る」の 1 通り。
・6 個の山: 目標値は $t = 2 \oplus 1 = 3$ 。移れるのは 5, 4, 3 個の状態で、グランディ数は $1, 0, 3$ である。 $3$ になるのは 3 個の状態だけなので、「3 個取る」の 1 通り。目標値 $3$ は元のグランディ数 $2$ より大きいが、実際に移れることに注意する。

手順 5（合計する）: $0 + 1 + 1 = 2$ 。念のため確かめると、5 個の山から 1 個取った後の局面は $2 \oplus 0 \oplus 2 = 0$ 、6 個の山から 3 個取った後の局面は $2 \oplus 1 \oplus 3 = 0$ で、どちらも全体のグランディ数が $0$ になっている。

よって、勝ちにつながる手は $2$ 個である。

答え: $2$

よくある誤り

各山のグランディ数を普通に足してしまう誤り。例題では $2 + 1 + 2 = 5$ としてしまう。正しくは 2 進法の排他的論理和で、 $2 \oplus 1 \oplus 2 = 1$ である。
石の個数そのもののニム和を計算してしまう誤り。例えば同じルール（1〜3 個取る）で山が $3$ 個と $7$ 個のとき、 $3 \oplus 7 = 4 \neq = 0$ だから勝てる、と判断してしまう。正しくはグランディ数どうしのニム和で、 $g (3) \oplus g (7) = 3 \oplus 3 = 0$ なので手番の人の負けである。
ニムと同じように「 $g_{i} \oplus G < g_{i}$ となる山だけを調べればよい」としてしまう誤り。例題では 6 個の山（ $g = 2$ 、目標値 $3$ ）を見落とす。正しくは、一般のゲームでは移り先のグランディ数が元より大きくなることもあるので、すべての山について表で移り先を確かめる。
1 つの山に勝ちにつながる手は高々 1 つだとしてしまう誤り。例えば取れる個数が ${1, 3, 4}$ のゲームで 4 個の山（ $g (4) = 2$ ）の目標値が $1$ のとき、移り先の 3 個の状態と 1 個の状態はどちらもグランディ数が $1$ なので、「1 個取る」と「3 個取る」の 2 通りがある。正しくは、目標値を持つ移り先をすべて数える。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

スプレイグ・グランディの定理と勝ちにつながる手

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題