yamake's blog

主に競プロ、たまに自転車

Nim(石取りゲーム)の必勝法

競技プログラミング

Nimで絶対に勝てる方法をこのブログを見ているあなたにだけお届け！！

なんと今回に限り、無料でNimの必勝法を教えちゃいます！！！

Nimに負け続けてお困りの方、生き別れの妹を賭けてNimで勝負の予定がある方、必見です！

今までNimの必勝法をあまり理解しないまま必勝法が存在することのみを覚えていて、毎回ググって勝利条件を調べていましたが、この問題の解法を考えている時によく整理できたのでまとめようと思います。

排他的論理和の説明->Nimの必勝法への応用

という順序で説明していきます。

排他的論理和 $xor$

排他的論理和 $xor$ : 2つの入力のどちらか一方のみが真の時のみ真を返す演算のこと。

f:id:yamakeeee:20201111070142p:plain — 排他的論理和ベン図

ビットごとの排他的論理和: 整数 $A,\ B$ を二進数表現した数値の各bitについて排他的論理和をとること。

ここでは以降ビットごとの排他的論理和も「排他的論理和」と呼び、整数同士の演算子として $xor$ を使用します。

3と5のビットごとの排他的論理和を例に取ると、

$3\ xor\ 5\\=011\ xor\ 101\\=110\\=6$

となります。

Nimをする上で必要になる排他的論理和の重要な性質がこちらになります。

$(S\ xor\ A)\ xor\ A=S$

これは排他的論理和はビットごとに「 $A$ のあるフラグが立っていれば $S$ の同じ位置のフラグを反転させる操作」であるので、二度繰り返すと元に戻るということを表しています。

参考

排他的論理和 - Wikipedia

Nim

Nimとは複数の石を積み上げてできた山を複数並べた場から、先手と後手が交互に任意の山を一つ選び任意の個数の石を取っていき、取れる石の無くなった方が負けになるゲーム*1です。

参考:

石取りゲーム

Nimの必勝法

Nimの必勝法を端的にまとめると、「『全ての山の石の個数の排他的論理和を取り、それが $0$ 』の状態で相手に手番を渡せたら勝ち。」です。

全ての山の石の個数の排他的論理和が $0$ でないところからは必ずこれを $0$ の状態にできるので、

「先手が始まるときに全ての山の石の個数の排他的論理和が $0$ でなければ勝利」が成り立ちます。

次に、これを説明します。

まず最初に全ての山の石の個数の排他的論理和を $S$ とします。

山の石の個数がそれぞれ $a_1, a_2, ..., a_N$ とすると、

$S=a_1\ xor\ a_2\ xor\ ...\ xor\ a_N$

となります。

Nimが終了した状態での $S$ は明らかに $0$ です。

$S$ について

(1) $S=0$ からは $0 \lt S'$ への遷移しかできない.

(2) $0 \lt S$ となる $S$ を $1$ 手で必ず $0$ にできる.

これら2つが言えると上の必勝法は正しいと言えます。

自分の手番を $S=0$ で終えると(1)により相手は $0 \lt S$ で手番を終え、そうなると(2)によって $S=0$ で自分の手番を終えられるからです。

(1)は

$0\ xor\ A=A$

からわかります。

(2)について考えます。

石が $A$ 個ある山から何個か石を取り出して石が $B$ 個になったとします。

このときの $S \rightarrow S'$ の変化は

$S'=S\ xor\ A\ xor\ B$

と表せます。

（『排他的論理和の重要な性質』より、排他的論理和の演算は「総和から $A$ の寄与を消す」という演算と「 $A$ をxorする」という演算が等価であるので。）

(2)が成り立つためには $S'=0$ が必要なので、 $B=S\ xor\ A$ となるように取れること、つまり $0 \lt S$ となる $S$ について石の個数 $A$ が

$S\ xor\ A \leq A$

を満たす山が存在すると証明できればればよいです。

全ての山の石の個数の排他的論理和 $S$ の一番大きいビットと同じ位置 $i$ にフラグが立っている山を見つけ、その山の石の個数を $A$ とします。

$S\ xor\ A$ について考えます。

$S$ も $A$ も $i$ 番目にフラグが立っているので

$S\ xor\ A$ の $i$ 番目のフラグは立ちません。

$0\leq j \leq i-1$ となる $j$ 番目のフラグに関して制限はありません。

したがって

$S\ xor\ A \leq \sum_{j=0}^{i-1}{2^j}$

が成り立ちます。

加えて、

$\sum_{j=0}^{i-1}{2^j} \lt 2^i \leq A$ より、

$S\ xor \ A \lt A$

が示されました。

以上より、 $S$ の一番大きいビットと同じ位置にフラグの立っている山からは操作後の石の個数 $B$ が

$B=S\ xor\ A$

となるように石を取り除くことができると証明できました。

*1:wikipediaによると山を用意してからじゃんけんなどで先手後手を決めるようですが、ここでは先手後手を決める前に山の構成を知ることはできないとします（そうしないとじゃんけんの必勝法が必要になるので）。