ゲームのルール
-
ルール
三つの山に分かれた石の山があります。二人が交互に山から石をとります．
一つの山からは任意の個数取ることができますが，二つの山に跨ってとることや，一つも取らないことは許されません．
石を取ることが出来なくなった方が負けです．
-
例
ゲームは，例えば，次のように進行します。3つの数が、実行後の各山の数です。
最初の三つの山の数を(4,3,2)とします．A:(2,3,2)でプレーヤAが最初の山から2個取ったことを示します．以下次のように進行します。
B：(2,3,1)，A:(2,1,1)， B:（0,1,1)，A:(0,0,1)， B:(0,0,0)でBの勝ちです．
-
マッチ棒を利用したゲームのようす
マッチ棒を三つの山にわけ、棒を取り合います。
（[数学ソフトタッチ」から）
2進数
-
10進数とは
このゲームは2進数を応用すると、必勝法を導くことができます。私たちは多くの場合、数字を10進数で表現します。10進数は 0,1,2 と順に数え 9 まで進むと、10 に対応する記号は利用せず、二つの記号を用いて 「１０」と表記します。左の１は「10」の桁で、「10」は 10 * 1 の意味ですね。10>11>12> と数え、19 の次は 20 となります。
どうように、「99」 のつぎは 3ケタの数となって「100」となりますね。
-
2進数
コンピュータは、オン（入り）とオフ（切り）を示す何百万という電子的なスイッチで構成されています。このスイッチのオンとオフの二つの記号を ０ と １ で表現すると、数を2進数で表すことができます。
この場合、０＞１＞１０（２）＞１１＞１００（４）＞１０１＞１１０＞１１１（７）＞１０００（８）
と数えます。（ ）の中は対応する10進数です。
2進数の上位の桁は、10進数では２のべき乗の値になります。ここで、2^5 は「２の5乗」の意味です。
1,2,4,8,16,32（2^5）,64,128,256,512,1024（2^10）、
ところで、指を折ったとき ０、伸ばした時を１とすると、5本の指で 31（2^5-1） まで、10本の指では 1023（2^10-1） まで数えることができます。ちょっと「練習」が必要ですがやってみてください。
演習 ３，６，９ を2進数で表示してください。
ヒント 小さな数の場合、1,2,4,8 で分解します。6の場合 4+2 と分解できますから 0110 となります。
-
2進数の演算
2進数の足し算方法は10進数の足し算の方法と変わりません。下の桁から桁上がりを考慮して順に計算します。２進数で和が（10進で）2以上の場合は、次の桁へ桁上げします。
0 0 1 0 + 0 1 1 0 ------------ 1 0 0 0
この計算は、10進数では、2 + 6 = 8 に相当します。
ここでは、足し算や掛け算でなく、「偶奇性」にもとづく演算を利用します（排他的論理和と呼ばれます）。演算を ^ でかき、これは演算対象の １ が偶数のとき０、奇数のとき１とします。0 ^ 1 ^ 0 = 1 で、0 ^ 1 ^ １ = ０ となります。実は、桁上げを考えない足し算と同じです。
演習
各桁を排他的論理和してください。
0 0 1 0 ^ 0 1 1 0 ------------ ? ? ? ?
これで準備ができました。
手法
-
必勝形
このゲームには必勝法があり、最初の山の数で（相手がどのように取っても）勝つ方が定まっています．簡単な場合では (0,n,n) の場合，後手が必勝です．後手は先手と同じだけ別の山から石を取り、常に(0,n,n)の形を保てば勝つことができます．また，(3,2,1)も後手必勝です．
-
一般的な必勝形
一般的な必勝法は次の通りです．各山の数を(a,b,c)とします。a,b,cをそれぞれ二進数に展開し，各桁を ai,bi,ci とします．このとき，すべての桁iについて ai ^ bi ^ ci = 0 のとき、必勝形とよびます。ここで、^ はEXOR（排他的論理和/偶奇性演算）で、1の数が偶数のとき0、奇数のとき1となります．
必勝形にすることができればゲームに勝つことができます。この必勝形に対し，ルールに従って石をとれば，必ず必勝形でなくなり、また，必勝形でない場合，適当に石をとれば必ず必勝形にできることが証明できます．
ここで、EXOR（排他的論理和）はつぎのような演算です。
A B A^B ０ 0 0 0 1 1 1 0 1 1 1 0
-
証明
必勝形から、どこか一つの山の数を減らすと、どこかの桁（ ai,bi,ci ）の0,1が変化するため、必勝形でなくなります（二つの山から減らすと必勝形にすることも可能です）。
必勝形でない形からは必勝形にすることが出来ます。必勝形でない一番大きな桁を0とすれば、それ以下の桁は好きな値に設定できます。したがって、必勝形にすることができます。
-
必勝形の例
（５，４，１）、 （６，４，２）、（７，５，２）、（７，４，３） などが必勝形です。各数を2進数で表現し、各桁ごとに偶奇性演算をし、すべて０になれば、必勝形です。
５： １ ０ １ ４： １ ０ ０ １： ０ ０ １ --------------- ０ ０ ０
-
演習
次の各場合の次の手（必勝形）を求めなさい。
（0,6,4)
(5,2,3)
(6,5,4)
(5,2,7)
プログラム手順
-
入力
ニムゲームの必勝形をプログラムで求めることは容易です。プログラムでは最初に各山の石の数を鍵盤から a[i] に読み込みます．0 以下の値の場合、再入力を促します。
ゲームは相手を先手とします。my_turn が0の場合相手、1の場合が計算機の番とします。また、各山の数の和をnumとし、これが0ならゲーム終了です。
numが0でない場合、繰り返しに入り、まず、各山の数を * で表示します。このとき、山の数の最大値(max)と最大となる山の番号(imax)を覚えておきます。
-
必勝形
計算機の番の場合、まず、必勝形か否かを判断します。必勝形の判断は、各山の数を a[0]、a[１]、a[２] とするとx = a[0] ^ a[1] ^ a[2]
x == 0 のとき必勝形です。
必勝形でなければ、必勝形にできる山を選択します。( a[i] > ( a[i] ^ x) ) となる山(i)から石をとれば必勝形になります。
a[i] ^ x a[0] = (1,0,1) (1,1,0) a[1] = (0,1,1) > (1,0,1) a[2] = (1,0,0) (1,1,0) x = (0,1,0)
既に必勝形になっている場合は，一番石が多い山から一つ石をとり，相手が間違えるのを待つこととします。
相手の番の場合、石をとる山の番号と石の数を問い合わせ、0以下や、取る数が現在の石の数より多い場合、再入力を促します。
プログラム（参考）
-
Cプログラム例
/*********************************************************** nim.c -- 三山くずし ***********************************************************/ #include <stdio.h> #include <stdlib.h> //奥村著：アルゴリズム辞典より void main() { int a[4], i, j, imax, max, n, r, x, my_turn; for (i = 1; i <= 3; i++) { printf("%d 番の山の石の数? ", i); scanf("%d", &a[i]); if (a[i] <= 0) return EXIT_FAILURE; } for (my_turn = 1; 1; my_turn ^= 1) { max = 0; for (i = 1; i <= 3; i++) { printf(" %d ", i); for (j = 1; j <= a[i]; j++) printf("*"); printf("\n"); if (a[i] > max) {//maxは最大値 max = a[i]; imax = i; } } if (max == 0) break;//繰り返し終了 if (my_turn) { printf("私の番です.\n"); x = a[1] ^ a[2] ^ a[3]; /* 排他的論理和 */ j = 0; for (i = 1; i <= 3; i++) if (a[i] > (a[i] ^ x)) j = i;//jから石を取る if (j != 0) a[j] ^= x; else a[imax]--;//必勝形になっている場合 } else {//相手の番 do { printf("何番の山からとりますか? "); r = scanf("%d", &i); // rは読んだ文字数 } while (r != 1 || i < 1 || i > 3 || a[i] == 0); do { printf("何個とりますか? "); r = scanf("%d", &n); } while (r != 1 || n <= 0 || n > a[i]); a[i] -= n; } } if (my_turn) printf("あなたの勝ちです!\n"); else printf("私の勝ちです!\n"); }
-
実行例
1 番の山の石の数? 5 2 番の山の石の数? 3 3 番の山の石の数? 2 1 ***** 2 *** 3 ** 私の番です. 1 * 2 *** 3 ** 何番の山からとりますか? 2 何個とりますか? 2 1 * 2 * 3 ** 私の番です. 1 * 2 * 3 何番の山からとりますか? 1 何個とりますか? 1 1 2 * 3 私の番です. 1 2 3 私の勝ちです!
アンケート
2進数による計数法は理解できましたか１．できた ２．たぶん ３．まだだめ
ゲームの必勝法は理解できましたか
１．できた ２．たぶん ３．まだだめ
必勝法の計算はできますか？
１．できた ２．たぶん ３．まだだめ
参考文献
ダン・ピトー：「数学ソフトタッチ」 白揚社