石取りゲームの必勝法を紹介します。
石取りゲームのルール
次の問題を考えます。
石の山が $N$ 個あります。山 $i (1 \leqq i \leqq N)$ には、$A_i$ 個の石があります。2人のプレーヤが次のゲームをします。
- 好きな石の山をひとつ選び、選んだ山から１個以上の石を好きなだけ取る。この操作はパスできない。
- 石が取れなくなったら負け。
先手が勝つか後手が勝つか判定してください。
簡単な場合から考える。
$N=1$ の場合
明らかに先手必勝です。ひとつの山から先手がすべての石を取ってしまえば、後手は取れる石がありません。
$N=2$ の場合
$A_1=1, A_2=1$ の場合
この場合は、後手必勝です。仮に先手が $A_1$ から石を取れば、後手は $A_2$ の石を取ります。この結果、先手は取れる石がなくなります。
$A_1=2, A_2=2$ の場合
この場合も、後手必勝（先手必敗）です。先手がどの山から石をとっても、後手は逆の山から同じ数の石を取ると、先手の手番で同じ個数の石の山が残ります。最終的に先手の手番で $A_1=1, A_2=1$ となるか、$A_1=0, A_2=0$ となります。このため、先手が負けます。
$A_1=3, A_2=2$ の場合
この場合は、先手必勝です。$A_1$ から1個取れば、後手番で $A_1=2, A_2=2$ となります。その結果、後手必敗となります。
$N=2$ の結論
上の考えを繰り返すことにより、以下のことが分かります。
- $A_1$ と $A_2$ の数が同じであれば、後手必勝
- $A_1$ と $A_2$ の数が異なれば、先手必勝、先手の初手で山の石の数を同じにして、後手の手番にします。
$N=3$ の場合
$A_1=1, A_2=2, A_3=3$ の場合
少し考えれば、後手必勝であることが分かります。先手がどのように石をとっても、後手の手番で、石の山を2つにして、その数を同じにすることができます。ここで先手の手番となるため、後手必勝（先手必敗）となります。
$A_1=1, A_2=2, A_3=4$ の場合
この場合は、先手必勝です。$A_3$ から1個取れば、上で考察した場合に帰着します。ここで後手の手番となるため、後手の負けとなります。
$N=3$ の結論
3つの山の石の数のXOR（排他的論理和）を計算します。この値が0以外であれば、先手必勝となります。逆にこの値が0であれば、後手必勝となります。
このXORの値を「ニム和」と呼びます。次のことが言えます。
- ニム和が0以外であれば、ある山から石をとって、ニム和を0にすることができます。
- ニム和の一番上の桁を持つ山の一番上の桁を1から0にするように石をとります。これより小さい桁は自由に動かせます。これにより全体のニム和を0にすることができます。
- ニム和が0であれば、どのように山から石をとっても、ニム和が0以外になります。
- すべての山の石がなくなれば、ニム和が0となります。
先手の手番でニム和が0以外であれば、ニム和を0にして後手の手番にできます。後手の手番では、ニム和が0以外となり、再び先手の手番となります。これを繰り返していけば、石の数が減っていくため、いつか後手の手番で石の山がすべて無くなります。
$N>3$ の場合
この場合も、$N=3$ の場合と同じです。石の山のニム和が0以外であれば、先手必勝です。ニム和が0であれば、後手必勝です。$N=3$ の場合と同じです。
最後に
XOR（排他的論理和）の興味深い応用でした。
