ニム

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

ニム (nim) は、2人で行うレクリエーション数学ゲームの1つである。ルーツは古代中国からあるとされ、16世紀初めの西欧で基本ルールが完成したが、名前については、一般的に1901年ハーバード大学のチャールズ・L.バウトン (Charles L. Bouton) によって名付けられたとされる。

このゲームの必勝法は、組合せ論による。組合せ論的には先手と後手どちらが勝つか、勝ちが保証されるためにはどのようにコインを取ればよいか、その勝利の戦略を決めることにある。

ゲームのルール[編集]

2人のプレイヤーがいくつかのコインの山からコインを取り合う。ゲームの目的は、最後のコインを取ることである。(コインの代わりに石や豆を使ってもよい)。

  • まず、コインの山を複数準備する。山の数や各山のコインの枚数は(プレイヤー同士で合意すれば)自由に決めてよい。
  • 2人のプレイヤーの順番は交互である。じゃんけん等で先手を決める。
  • 各々のプレイヤーは自分の順番のとき、コインの山を1つ選んでその山から1枚以上のコインを取り去る。(複数の山からコインを取ったり、コインを一枚も取らなかったりするのは反則である)。これが終わったら次のプレイヤーの手番になる。
  • すべての山のコインがなくなったとき、ゲームは終わりである。そして、最後のコイン(複数のときもある)を取ったときのプレイヤーが勝者である。

必勝法[編集]

山が二つの場合[編集]

特殊な場合として、2つのコインの山AとBでそれぞれの山のコインの数をa枚、b枚とする。このときの必勝法を考える。まずAとBの山のコインの数が異なるときを考える。先手は、AとBの山のコインの数が同じになるように、コインの数の多い方の山からコインを取る。そのあと、先手は自分の順番のとき、後手の取るのを真似ればよい。つまり、後手が片方の山からc枚コインを取ったとしたら、先手はもう一方の山から、同じ数のc枚だけコインを取ればよい。これが先手の必勝法である。

もしAとBの山の数が同じならば、先手の取るのを真似ることで後手が勝つことになる。

一般の場合[編集]

一般的な必勝法として、排他的論理和を用いたものが知られている。

すなわち、山の数をnとし、i番目の山のコインの枚数をaiとするとき、各aiを二進数展開したときのビット毎の排他的論理和の全ての桁が0になるようコインを取ればよい。

詳細はこの記事の英語版、もしくは下記の参考文献を参照

双対ゲーム[編集]

ニムの勝ち負けを反転させたゲームを、ニムの双対ゲームと呼ぶ。 すなわち、双対ゲームはニムと同じルールでゲームが展開していくが、通常のニムと違い最後のコインを取った方が負けになる。

双対ゲームの必勝法はニムの必勝法を反転させたものになっていない。

これに関しても詳細は前掲書を参照。

関連項目[編集]