コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

ニム

出典: フリー百科事典『ウィキペディア(Wikipedia)』

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

歴史的には、最初に必勝法が数学的に解決したゲームである[1]。最善手を行うならば、どちらが勝つかは最初の個数の組で決まる(後述)。その必勝法と証明は組合せ論による。

ゲームのルール

[編集]

有限個のコイン(石や豆でもよい)の山を有限個用意する。2人のプレイヤーが山からコインを好きな数ずつ交互に取り合っていく。

  • 一度に取るコインは1つの山からとする。
  • 回ごとに最低1個は取らなければいけないとする。

これを繰り返すと有限回で全てのコインがなくなるが、最後にコイン(複数でもよい)を取ったプレイヤーにより勝敗を決める。最後にコインを取った者を勝者とするルールは正規形と呼ばれている。

必勝法

[編集]

山が2つの場合

[編集]

特に山が2個の場合は、一般の場合よりも必勝法が簡単である。

山A, Bのコインの個数をそれぞれ a, b とする。調べ上げていっても容易に類推されるように、後手必勝形は a = b のときのみである。ab ならば、先手が多い山から ab の差だけコインを取ると、次に相手は ab にせざるを得なくなる。先手がこれを繰り返すと必ず勝つ。

a = b ならば、後手が上記を実行すると必ず勝つ。

一般の場合

[編集]

コインの山の数を n とし、各山のコインの枚数を A1, …, An とする。

とおく。ただし、ビットごとの排他的論理和ニム和)を表すものとする。

S ≠ 0 のときは 必ず S = 0 にでき、すると次に相手は S ≠ 0 にせざるを得なくなる。これを繰り返すと必ず勝てる。S ≠ 0 ならば先手必勝、S = 0 ならば後手必勝にできる。

証明

[編集]

先手が SAk からコインを取り除いて Bk になったとする。

とおく。排他的論理和は交換法則結合法則および を満たすため、次の等式が成り立つ。

次の2つの補題から従う。

補題1 のとき、任意の操作について である。

証明: であることから明らかである。

補題2 のとき、ある操作について である。

証明:S の ビットのうち 0 でない最高位を 2d の位とする。Ak2d の位が 0 でない k を1つ選ぶ(このような k は必ず存在する)。 であるため、k番目の山から何枚かのコインを取り除いて 枚にすることができる。このとき となる。

逆形

[編集]

最後にコインを取った者を負けとするルールは「逆形」[2]「逆型」「双対ゲーム」などと呼ばれている。一般に、組合せゲームの正規形と逆形では、プレイヤーが逆のことに最善を尽くすため、正規形の後手必勝形が逆形の後手必敗形とはなっていない。

実際に逆形ニムにおいては、必勝形、必勝法は次の通りである[3]

n個の山の内、コインが2個以上であるものの個数を i とする。

i = 0 である後手必勝形は

  • 1個だけの山が奇数個のみ。… (1)

である。

i = 1 のときは、

  • 1個だけの山が奇数個なら、2個以上の山を空にすることで必勝形にできる。
  • 1個だけの山が偶数個なら、2個以上の山を1個にすることで必勝形にできる。

故に i = 1 のときは必敗形である。

i ≥ 2 のときは、プレイヤーがニム和を 0 にし続ければ、相手は i = 1 にせざるを得なくなる。

(なぜなら、 i = 1 のときのニム和は 0 でないから。)

故に、必勝形 (A1, …, An)

  • (1) または
  • 2個以上の山が2個以上かつ、ニム和が 0 であるもの。

に限られる。//

脚注

[編集]

関連項目

[編集]

外部リンク

[編集]