石の山をいくつか並べ、2人が交互に石を取っていきます。ルールは2つだけです。1回の番で取れるのは1つの山からだけで、1個から山全部まで好きな数だけ取れます。そして最後の石を取った人の勝ちです。ルールはこれほど単純なのに、驚いたことに、ゲームが始まる前から誰が勝つかを完全に予測する方法があるのです。
秘密は、各山の石の数をXOR(排他的論理和)という演算で計算することです。XORは2つの数を2進法で桁ごとに比べ、それぞれの桁で数字が同じなら0、違えば1を返します。たとえば山が[3, 4, 5]なら、2進法では3=011、4=100、5=101です。桁ごとにXORをとると、1桁目は0⊕1⊕1=0、2桁目は1⊕0⊕0=1、3桁目は1⊕0⊕1=0。つまりXORの値は010、すなわち2です。
このXORの値(「ニム和」と呼びます)が0でないなら、いま手番の人には必ず勝てる手があります。各山の数とXORの値そのものとのXORをとり、結果がもとの数より小さくなる山を探せばよいのです。[3,4,5]ではXORは2でした。5 XOR 2=7と4 XOR 2=6はどちらも大きくなるのでだめですが、3 XOR 2=1は小さくなるので使えます。そこで1番目の山(3個)から2個取って1個だけ残すと、山は[1,4,5]になり、そのXORは1⊕4⊕5=0になります。
反対に、XORがすでに0なら、いま手番の人が不利です。相手が完璧に指す限り、どんな手を打ってもXORは0以外に変わり、相手は毎回それを0に戻すだけで、最後には相手が最後の石を取ることになります。だからニムの必勝法は驚くほど単純で、「自分の番を終えるときに、いつもXORを0にしておく」ことなのです。
なぜXORだとうまくいくのでしょうか?XORには「ペアになるものを打ち消し合う」という性質があります。ゲームが終わったとき(すべての山が0)、XORも当然0です。そしてXORが0の状態から山を1つだけ変えると、必ず0ではなくなります(1つの山だけを変えるとつり合いがくずれるからです)。逆にXORが0でないときは、そのずれをちょうど打ち消せる山が必ずあり、XORを0に戻せます。この2つの性質が組み合わさって、「XOR=0の状態で相手に番を渡し続ければ、最後には相手が追いつめられる」という必勝法が成り立つのです。
アクティビティのページでは、コンピューターがまさにこのXOR作戦で指してくるので、コンピューターが有利な局面から始まると、本当に勝つのは難しいです。でも、ヒントボタンで毎回XORの値とおすすめの手を確かめれば、あなたもコンピューターに勝てます。いろいろな山の組み合わせを試して、最初にXORが0(つまり自分が不利)かどうかを確かめる習慣をつけてみましょう。