ニム

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

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

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

ゲームのルール[編集]

2人のプレイヤーがいくつかのコイン(または石、豆など)の山からコインを取り合う。ゲームの目的は最後のコインを取ることである。

  • 2人のプレイヤーの順番は交互である
  • 各々のプレイヤーは自分の順番のとき、コインの山をひとつ選んでその山から1枚以上コインを取る。

すべての山のコインがなくなったとき、ゲームは終わりである。そして、最後のコイン(複数のときもある)を取ったときのプレイヤーが勝者である。

必勝法[編集]

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

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

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