1. 高校数学の美しい物語
  2. ニム(複数山の石取りゲーム)の必勝法

ニム(複数山の石取りゲーム)の必勝法

更新日時 2021/03/07

ニム,山崩しゲーム,石取りゲームなどと呼ばれるゲームについて。ニムには2進法を用いた必勝法があります。

目次
  • ニムのルールと例

  • 必勝形について

  • ニムの必勝法の概略

  • 必勝法であることの証明

ニムのルールと例

ニムにはいろいろなバージョンがあるようですが,今回解説するのは以下のルールです。

  • 二人で行うゲーム。
  • いくつかの山にいくつかの石がある。
  • プレーヤーは交互に石を取っていく。このとき同時に取れるのは同じ山の石のみ。1回で1個以上最大何個でも取れる。

・最後の石を取った方が勝ち。

以下では山の石の数を並べて (a,b,c)(a,b,c) などと表します。例えば (3,5,7)(3,5,7) は石の数が3の山,5の山,7の山が1つずつある状況です。また,プレーヤーを A,BA,B とします。

(3,5,7)(3,5,7) からスタートする。

AA が一つ目の山から2つ取る:残り (1,5,7)(1,5,7)

BB が三つ目の山から7つ全部取る:残り (1,5)(1,5)

AA が二つ目の山から4つ取る:残り (1,1)(1,1)

BB が二つ目の山から1つ取る:残り (1)(1)

AA が最後の石をとって勝利

必勝形について

ニムの必勝法について説明するための準備として「必勝形」なるものを定義します。

以下の状態を「必勝形」と言うことにします:

各山の石の数を2進数で表したとき,各桁の和が全て偶数である状態

(各桁の排他的論理和が 00 であるような状態)

例1

(2,5,7)(2,5,7) は2進数で表すと,

10,101,11110,101,111 となる。各桁を足し算すると 222222 (排他的論理和は 000000 )となり全て偶数なので必勝形。

例2

(2,3,3)(2,3,3) は2進数で表すと,

10,11,1110,11,11 となる。各々を足し算すると 3232 (排他的論理和は 1010 )となり奇数が存在するので必勝形でない。

排他的論理和 1010 のことを (2,3,3)(2,3,3)ニム和と言ったりもします。

ちなみに,山が二つのときは,

(a,b)(a,b) が必勝形     a=b\iff a=b となります。

確認してみてください。

ニムの必勝法の概略

ニムには「必勝法」が存在します。 自分の手番終了後に必勝形に持っていけば勝てるというものです。

※「必勝形」と言うとその状態で回ってきた方が有利っぽいので本当は「必敗形」と呼ぶべきかもしれませんが説明の都合上,ご容赦下さいm(__)m

スタートが「必勝形でない状態」ならば以下のようにすることで先手が勝てます。

スタートが「必勝形」なら立場が逆転するので後手が勝てます。

「必勝形でない状態」からスタートしたときの先手必勝法

1: 「必勝形でない状態」からうまく石を取れば「必勝形」になるので自分の手番終了後は常に「必勝形」になる。

2: 「必勝形」からどのように石を取っても「必勝形でない状態」になるので相手の手番終了後は常に「必勝形でない状態」になる。

3:石がない状態(終了状態)は「必勝形」なので,終了状態は自分の手番終了後に来るはず!

3は自明ですが,1,2でうまくいく(赤字部分が正しい)ことは証明しなければなりません。とは言っても両方ともけっこう簡単です。

必勝法であることの証明

※1についての説明が大きく間違っていたので,修正いたしました(2017/9/2)。ご指摘いただきありがとうございましたm(_ _)m

1について:

「全ての山のニム和」において 11 である桁を反転させるような石の除き方をしたい。それは, ニム和の最高位が 11 である山 XX を選ぶことで実現できる。

(2,4,5)(2,4,5) のとき。

(2,4,5)(2,4,5) は二進法で,(10,100,101)(10,100,101) であり,ニム和は 011011 となる。よって,1桁目と2桁目を反転させるような石の除き方をすればよい。

どの山から何個石を除くか?

ニム和の最高位は2桁目なので,2桁目が 11 である山を選ぶ。つまり「 1010 」の山(石の数が 22 つの山)を選ぶ。

反転させたい桁(1桁目と2桁目)を反転させると 0101 になる。つまり,この山の石の数を n=1n=1 個にすればOK。

まとめると,22 の山の石を n=1n=1 個にすることで必勝形にできる。

(ニム和の最高位が 11 である山を選んでいるので,反転させた後の数 nn がもともとの石の数より小さくなる。すなわち,石を除くことで山 XX の石の数を必ず nn 個にできる。)

2について:(全体のうち残りはそのままで 11 つだけ値を変えるとどこかの桁の排他的論理和は必ず変わるので)どのように石を取ってもニム和は変化してしまいます。そのため必勝形(=ニム和が 00 である状態)からどのように石を取っても「必勝形でない状態」になります。

※頭脳王で登場した考察ゲームは最後の石をとった人が負けというルールでした。ほとんど同様に必勝法が作れます。

友達とニムをやりたくなりますが,実戦で毎回2進数の和をカリカリ計算するのはなんかカッコ悪いですね。

Tag:難しめの数学雑学・ネタまとめ

人気記事
  1. 高校数学の美しい物語
  2. ニム(複数山の石取りゲーム)の必勝法