2014/12/22

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

分野: 場合の数  レベル: マニアック

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

ニムのルールと例

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

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

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

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

$(3,5,7)$ からスタートする。
$A$ が一つ目の山から2つ取る:残り$(1,5,7)$
$B$ が三つ目の山から7つ全部取る:残り$(1,5)$
$A$ が二つ目の山から4つ取る:残り$(1,1)$
$B$ が二つ目の山から1つ取る:残り$(1)$
$A$ が最後の石をとって勝利

必勝形について

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

以下の状態を「必勝形」と言うことにします:
各山の石の数を2進数で表したとき,各桁の和が全て偶数である状態
(各桁の排他的論理和が $0$ であるような状態)

例1

$(2,5,7)$ は2進数で表すと,
$10,101,111$ となる。各桁を足し算すると $222$(排他的論理和は $000$)となり全て偶数なので必勝形。

例2

$(2,3,3)$ は2進数で表すと,
$10,11,11$ となる。各々を足し算すると $32$(排他的論理和は $10$)となり奇数が存在するので必勝形でない。

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

ちなみに,山が二つのときは,
$(a,b)$ が必勝形 $\iff a=b$ となります。
確認してみてください。

ニムの必勝法の概略

ニムには「必勝法」が存在します。自分の手番終了後に必勝形に持っていけば勝てるというものです。
※「必勝形」と言うとその状態で回ってきた方が有利っぽいので本当は「必敗形」と呼ぶべきかもしれませんが説明の都合上,ご容赦下さいm(__)m

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

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

1:「必勝形でない状態」からうまく石を取れば「必勝形」になるので自分の手番終了後は常に「必勝形」になる。
2:「必勝形」からどのように石を取っても「必勝形でない状態」になるので相手の手番終了後は常に「必勝形でない状態」になる。
3:石がない状態(終了状態)は「必勝形」なので,終了状態は自分の手番終了後に来るはず!

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

必勝法であることの証明

1について:一番数の大きい山から適切な個数石を取ればニム和を $0$ にできます。具体的には一番大きい山以外のニム和を打ち消すような個数残せばOKです。

$(2,3,3,5)$ のとき。
一番数の大きい山以外の山$(2,3,3)$ のニム和は $10$ であった。よって,これを打ち消すような数 $10$ が欲しい。よって,$5$ の山から3つ石を取れば$(2,3,3,2)$ となりニム和は $0$ となる。つまり必勝形にできた。

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


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

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

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

分野: 場合の数  レベル: マニアック