当ＨＰにおいて、いろいろなところにニムゲームに関する話題が取り上げられている。
お茶の時間 パズル＆クイズ の中の、「石取りゲーム」「石取りゲーム（２）」
「石取りゲーム（３）」「石取りゲーム（４）」「石取りゲーム２０２０」「三山崩しゲーム」など。
また、投稿一覧の中の、「石取りゲーム」など。
そもそも「ニム（ｎｉｍ）」とは、２人で行うゲームで、交互に石を取り合い勝者を決めるもの
を言う。この名前は、１９０１年にバウトン（ハーバード大学）によって名付けられたとのこと
である。 日本では、山崩しゲームとか石取りゲームなどと呼ばれる場合もがある。
ニムゲームには必勝法があり、二進法を用いて説明される。
交互に山の一つを選んで、そこから好きなだけの石を取る。２つ以上の山には同時に手を
つけない。最後に石を取り除いた人が勝ちとする。
・各山の石の個数を２進法で表し、各桁（ビット）毎の和を求める。
この和は、排他的論理和（２つの値が一致しないときに値１を返す）で求められ、ニム和
とも呼ばれる。
各桁毎の和がすべて０ → 先手必敗
各桁毎の和が一つでも１ → 先手必勝
であることが知られている。
例 山をＡ（２個）、Ｂ（１個） とする。
先手が勝つためには、Ａから１個とり、Ａ、Ｂ同数にして後手に手を渡す。
後手は、どちらか（Ａとする）から１個取ると、先手はＢから１個取って、先手勝ちとなる。
石の個数を２進法で表すと、 Ａ（１０）、Ｂ（０１）
このとき、各桁毎の和は、 １、１ となり、一つでも１があるので、先手必勝となる。
例 山をＡ（３個）、Ｂ（２個） とする。
先手が勝つためには、Ａから１個とり、Ａ、Ｂ同数にして後手に手を渡す。
後手は、どちらか（Ａとする）から１個または２個取るしかないが、先手はＢから後手が取っ
た数を取れば、必ず先手勝ちとなる。
石の個数を２進法で表すと、 Ａ（１１）、Ｂ（１０）
このとき、各桁毎の和は、 ０、１ となり、一つ１があるので、先手必勝となる。
例 山をＡ（３個）、Ｂ（３個） とする。
先手がどのように石をとっても、Ａ、Ｂ同数が崩れてしまうので、必ず後手勝ちとなる。
石の個数を２進法で表すと、 Ａ（１１）、Ｂ（１１）
このとき、各桁毎の和は、 ０、０ となり、すべて０となるので、先手必敗となる。
例 山をＡ（３個）、Ｂ（４個）、Ｃ（５個）とする。
石の個数を２進法で表すと、 Ａ（１１）、Ｂ（１００）、Ｃ（１０１）
このとき、各桁毎の和は、 ０、１、０ なので、一つ１があるので、先手必勝となる。
勝ち方の例としては、次の通りである。
各桁毎の和で、１をなくし全て０にして手を渡せば、渡された方が必敗となる。
そこで、Ａから２個とると、 Ａ（１個）、Ｂ（４個）、Ｃ（５個） で、Ａ（０１）、Ｂ（１００）、Ｃ（１０１）
このとき、各桁毎の和は、 ０、０、０ なので、後手必敗である。
次に例えば、後手がＢから３個取ると、 Ａ（０１）、Ｂ（０１）、Ｃ（１０１）
このとき、各桁毎の和は、 １、０、１ で、一つでも１があるので、先手必勝となる。
次に、各桁毎の和をすべて０にして後手に手を渡すためには、先手は、Ｃから５個全部
取ればよい。このとき、Ａ（１個）、Ｂ（１個）、Ｃ（０個）で、Ａ（０１）、Ｂ（０１）、Ｃ（００）から、各桁
毎の和は、０、０ で、後手必敗である。後は言うまでもなく、簡単な手順で先手の勝ちとなる。
問 題 交互に１枚以上５枚以下のカードを取り続け、最後にカードを取った方が負けと
なるゲームがある。
（１） ７枚のカードの場合、勝つのは先手か後手か？
（２） ２３枚のカードの場合、先手が勝つためには最初何枚取るか？
（解）（１） 先手が１～５枚のカードを取ると残りは、２～６枚
よって、後手は、最後に１枚残すようにカードが取れるので、後手必勝である。
（２） 先手・後手合わせて６枚になるように取り続け、カードの枚数が７枚になったときに、
手を相手に渡せば必ず勝てる。
よって、カードの枚数が、 ７ 、１３＝７＋６ 、１９＝７＋６＋６ 、・・・ では必ず後手必勝
２３枚のカードの場合、先手が勝つためには、４枚カードをとり、１９枚にして相手に手を渡
せば、先手必勝である。 （終）
（追記） 「制限非不偏ニム」と題して、当ＨＰがいつもお世話になっているＨＮ「なお」さんから
ご投稿いただきました。（令和２年１２月７日付け）
ｎ個の石の山からA、Bの２人が交互に石を取るゲームをする。ただし、
Aが一度に取れるのは1個、4個、6個のいずれか
Bが一度に取れるのは2個、3個、5個のいずれか
とする。お互い最善の手を打ち合い最後の石を取った人を勝ち(打つ手の無くなった方の負
け)とする。
ｎ＝2020 ではこのゲームの結果は次のどれになるか？
①先手番が必ず勝つ
②後手番が必ず勝つ
③どちらが先手でもAが必ず勝つ
④どちらが先手でもBが必ず勝つ
らすかるさんからのコメントです。（令和２年１２月８日付け）
③です。具体的な勝ち方は、Aが先手のとき、最初は6個とる。後は、Bが2個ならAは1個、
Bが3個ならAは6個、Bが5個ならAは4個とる。
2+1≡3+6≡5+4≡0 (mod3) かつ 2020≡1 (mod3) なので、これを繰り返すことにより
必ずBの番で、残りが1個または4個または7個という状態になります。
残りが1個ならば、Bは取れませんのでAの勝ちです。
残りが4個ならば、Bは2個か3個しか取れませんが、いずれの場合も、Aは1個取れば勝ち
です。
残りが7個ならば、Bが2個とった場合はAが1個とれば残りが4個となり上と同じ
Bが3個とった場合はAは4個取って勝ち
Bが5個とった場合はAが1個取ればBは取れないのでAの勝ち
となり、いずれの場合もAの勝ちとなります。
ちなみに、ｎ個のときの結果をa[n]と表すことにして計算すると、a[n]は
3,1,4,3,1,1,3,1,2,
3,1,4,3,1,1,3,1,2,
3,1,4,3,1,1,3,1,2,…
という周期9の繰り返しになりますので、
・十分多い数の石をランダムに用意する（例えば石の代わりにゴマにしてひとつかみとるなど）
・先手後手はじゃんけんで決める（勝率1/2ずつとする）
とすると、Aの勝率が11/18、Bの勝率が7/18となり、最初からAに有利なルールです。
ただし、これは「十分多い数」がいくつであるかを最初に数えてわかっている場合に限られ
ます。いくつあるかわからない場合は、残り個数を先に把握できた人が有利ですね。
なおさんからのコメントです。（令和２年１２月９日付け）
正解です。このゲームでは帰結類の周期がピッタリ9ですが、設定を変えて色々調べると
面白いですね。非不偏ゲームの周期性についてはどの程度のことが知られているのか興
味あります
例えば、二人の取れる石数が有限個ならば、nが十分大きいところでは帰結類は常に周
期的でしょうか？
らすかるさんからのコメントです。（令和２年１２月９日付け）
「二人の取れる石数が有限個ならば」が「二人の取れる石数の上限があれば」という意味
なら、nの結果はn-1～n-(その上限)の結果で定まりますので、周期的になるはずです。
（そのパターンが有限通りなので）
なおさんからのコメントです。（令和２年１２月１０日付け）
確かに有限ですね。一般には周期の長さを求めるのは難しそうです。
（追記） 「ニム変形」と題して、当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんよりご投稿
いただきました。（令和２年１２月１１日付け）
2人が、n個のチップをまとめた山を用意して、先手は好きな数のチップを取り除く。ただし
全部の山を取り除くことは出来ないものとする。プレイヤーは交互にチップを取り除くが、
”前のプレイヤーが取った数の倍を超えて取ることは出来ないとする。”
最後のチップを取り除いた方が勝ちとする。（→ 参考：「２倍取りゲーム」）
（例） n=11 とする。A:3(残り8) なら、Bは1～6（個）を任意に選べてチップがとれる。B:2(6)
とする。Aは1～4（個）を任意に選べてチップがとれる。A:1(5)とする。Bは1か2（個）チッ
プがとれる。B:1(4) とする。A:1(3)、B:1(2)、A:2(0)となり、Aの勝ちとなる。
そこで、n=1000 である場合、先手Aが必ず勝利を勝ち取るためには、最初何個のチップを
とればよいか？
DD++さんからのコメントです。（令和２年１２月１１日付け）
ゼッケンドルフの定理を考えて、1000=987+13 なので 13 個。