ニム
(ニム・ゲーム から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/06/08 02:19 UTC 版)
ニム (英: Nim) は、2人で行うレクリエーション数学ゲーム（組合せゲーム）の一つである。起源は古代中国からあるとされ、16世紀初めの西欧で基本ルールが完成したが、名前については、一般的に1901年にハーバード大学のチャールズ・L・バウトンによって名付けられたとされる。
歴史的には、最初に必勝法が数学的に解決したゲームである[1]。最善手を行うならば、どちらが勝つかは最初の個数の組で決まる（後述）。その必勝法と証明は組合せ論による。
ゲームのルール
有限個のコイン（石や豆でもよい）の山を有限個用意する。2人のプレイヤーが山からコインを好きな数ずつ交互に取り合っていく。
- 一度に取るコインは1つの山からとする。
- 回ごとに最低1個は取らなければいけないとする。
これを繰り返すと有限回で全てのコインがなくなるが、最後にコイン（複数でもよい）を取ったプレイヤーにより勝敗を決める。最後にコインを取った者を勝者とするルールは正規形と呼ばれている。
必勝法
山が2つの場合
特に山が2個の場合は、一般の場合よりも必勝法が簡単である。
山A, Bのコインの個数をそれぞれ a, b とする。調べ上げていっても容易に類推されるように、後手必勝形は a = b のときのみである。a ≠ b ならば、先手が多い山から a と b の差だけコインを取ると、次に相手は a ≠ b にせざるを得なくなる。先手がこれを繰り返すと必ず勝つ。
a = b ならば、後手が上記を実行すると必ず勝つ。
一般の場合
コインの山の数を n とし、各山のコインの枚数を A1, …, An とする。
この項目は、ゲームに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。
- ニム・ゲームのページへのリンク
