2進数 その2

 昔からあるゲームに「三山くずし」があります。三つの山にそれぞれ石を積み上げ、二人交互に一つの山から(二つの山にまたがってはいけません)1個以上の石を取り合い、最後の石を取った方が勝ち、または最後の石を取らざるを得なくなった方が負け、のゲームです。但しこのゲームには必勝法があります。
 二つの山ならば、必勝法はすぐに判ります。キーワードは、「同数」。石の数を同じになるようにして、相手の手番にすればよいのです。最終的な数は、2-2。最後は、勝ちの形態で取り方を変えます。
 三山の場合の最終的な数は、1-2-3 です。同じくキーワードは「同数」です。但し10進数で、1+2=3 と考えてしまってはいけません。10進数では同数は一義的には決まりません。例えば石の数が 8-6-5 のとき、石を取って 1-6-5 とできますが、8-3-5 とも 8-6-2 ともできます。それならばどうするか。ここで、0か1かで決まってしまう真打ち2進数の登場です。
 先の 1-2-3 は、それぞれを2進数で表すと、1は 001、2は 010、3は 011 です。それぞれのビットに立つ1は2個(偶数個)になっています。この状況は一義的に決まり、相手はこの関係を崩すことしかできず、あなたは再び偶数個にして相手に手番を渡せば必ず勝てます。先ほどの 8-6-5 では、8は 1000、6は 0110、5は 0101 ですから、ビット毎の1を偶数個にするには、8を 0011 に、つまり3にすれば良いわけです。
 あえて偶数個と言ったのは、このゲームは三山に限らず、四山でも五山でもそれ以上でも同じだからです。四山の最終的な数は 1-1-2-2 、五山では 1-1-1-2-3 です。山が多くてもゲームが進行すれば一山減り、二山減り、・・となってゆき、最後は三山での争いになるので、「三山くずし」のゲームとして残ったのです。

se.gif