Loading AI tools
ウィキペディアから
ニム (英: Nim) は、2人で行うレクリエーション数学ゲーム(組合せゲーム)の一つである。起源は古代中国からあるとされ、16世紀初めの西欧で基本ルールが完成したが、名前については、一般的に1901年にハーバード大学のチャールズ・L・バウトンによって名付けられたとされる。
歴史的には、最初に必勝法が数学的に解決したゲームである[1]。最善手を行うならば、どちらが勝つかは最初の個数の組で決まる(後述)。その必勝法と証明は組合せ論による。
有限個のコイン(石や豆でもよい)の山を有限個用意する。2人のプレイヤーが山からコインを好きな数ずつ交互に取り合っていく。
これを繰り返すと有限回で全てのコインがなくなるが、最後にコイン(複数でもよい)を取ったプレイヤーにより勝敗を決める。最後にコインを取った者を勝者とするルールは正規形と呼ばれている。
特に山が2個の場合は、一般の場合よりも必勝法が簡単である。
山A, Bのコインの個数をそれぞれ a, b とする。調べ上げていっても容易に類推されるように、後手必勝形は a = b のときのみである。a ≠ b ならば、先手が多い山から a と b の差だけコインを取ると、次に相手は a ≠ b にせざるを得なくなる。先手がこれを繰り返すと必ず勝つ。
a = b ならば、後手が上記を実行すると必ず勝つ。
コインの山の数を n とし、各山のコインの枚数を A1, …, An とする。
とおく。ただし、 はビットごとの排他的論理和(ニム和)を表すものとする。
S ≠ 0 のときは 必ず S = 0 にでき、すると次に相手は S ≠ 0 にせざるを得なくなる。これを繰り返すと必ず勝てる。S ≠ 0 ならば先手必勝、S = 0 ならば後手必勝にできる。
先手が S の Ak からコインを取り除いて Bk になったとする。
とおく。排他的論理和は交換法則、結合法則および を満たすため、次の等式が成り立つ。
次の2つの補題から従う。
補題1: のとき、任意の操作について である。
証明: であることから明らかである。
補題2: のとき、ある操作について である。
証明:S の ビットのうち 0 でない最高位を 2d の位とする。Ak の 2d の位が 0 でない k を1つ選ぶ(このような k は必ず存在する)。 であるため、k番目の山から何枚かのコインを取り除いて 枚にすることができる。このとき となる。
最後にコインを取った者を負けとするルールは「逆形」[2]「逆型」「双対ゲーム」などと呼ばれている。一般に、組合せゲームの正規形と逆形では、プレイヤーが逆のことに最善を尽くすため、正規形の後手必勝形が逆形の後手必敗形とはなっていない。
実際に逆形ニムにおいては、必勝形、必勝法は次の通りである[3]:
n個の山の内、コインが2個以上であるものの個数を i とする。
i = 0 である後手必勝形は
である。
i = 1 のときは、
故に i = 1 のときは必敗形である。
i ≥ 2 のときは、プレイヤーがニム和を 0 にし続ければ、相手は i = 1 にせざるを得なくなる。
(なぜなら、 i = 1 のときのニム和は 0 でないから。)
故に、必勝形 (A1, …, An) は
に限られる。//
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.