はじめに

前日、AtCoder Regular Contest 105 で、NIMを応用させた問題が出題されました
それを受けて、この機会に復習することにしました

この手の知見をまとめた記事は飽和しているかと思いますが、自分の思考を整理するためにも記事にしてみました

NIMについて簡単に

NIMを知っていますか？私は知っています（なのにLet's Play NimがACできませんでした...）

NIMとは、二人零和有限確定完全情報ゲームの一つです*1

簡単に説明します

$n$ 個の石の山があります。二人のプレイヤーは交互に山を選んで、選んだ山から好きな数だけ石を取っていきます（必ず一つ以上取ります）先に石を取れなくなったプレイヤーの負けです。（= 最後に石を取ったプレイヤーの勝ちです）

このようなゲームのことをNIMといいます

NIMの必勝法

???「このゲームには必勝法がある。」

本当にあります。簡単な場合から考えてみましょう。

$n = 1$ としてみます

この場合は（石の数に関係なく）先手が必勝ですね。石を全て取ってしまいましょう。

$n = 2$ ではどうでしょうか

この場合は場合分けが必要です。
まず、どちらの山にも同じ数の石があるとしてみましょう。
この場合、後手が必勝なのはわかるでしょうか？

先手が選んだ山と逆を選んで同じ数の石を取り続けた場合、石の数が $(0,0)$ になるまでそれを続けることが出来ますね？そうなれば、最後のターン、先手は石を取ることができません。つまり、後手に必勝法があるわけです。

それでは、二つの山で石の数が違う場合はどうでしょう？
この場合、先手が勝つことができます。多いほうの山から石を取ってどちらの山の石の数も同じにしてしまえば、さきほどの後手の必勝法を先手が使うことができます。

さて、ここからが難しいです。

$n = 3$ ではどうなるでしょうか

うーん、、、場合分けをするにしても、なかなか大変な気がします

ここで、予備知識です

みなさんは、Grundy数というものを知っているでしょうか？

ゲームの状態を数字で表したもので、ざっくりいうと $0$ の時は負け、それ以外は勝ちを表しています。

もう少しちゃんというと、現在の状態から推移できる状態を表すGrundy数の集合のmex（集合に存在しない最小の非負整数）が、現在の状態を表すGrundy数となります。

定義だけ言われてもよくわからないというのが世の常です具体例を見てみましょう

21ゲームというものをやったことがあるでしょうか？0から初めて、1～3つまで数字を増加させるということを交互に繰り返し、先に21を言ってはいけません、というものです。

このゲームのGrundy数を求めてみます。

20で自分に回ってきたらどうあがいても負けてしまいますね？つまりGrundy数は0です。そこから始めていきましょう。

今の数	20	19	18	17	...	0
Grundy数	0

19からは20にのみ行けるので、0以外で最小の非負整数である1です
18からは19と20に行けるので、0,1以外で最小の非負整数である2です

という感じです

今の数	20	19	18	17	...	0
Grundy数	0	1	2

同じように埋めていきます

今の数	20	19	18	17	16	15	14	13	...	4	3	2	1	0
Grundy数	0	1	2	3	0	1	2	3	...	0	1	2	3	0

ということで、0のときのGrundy数は0、つまりお互いが最善手を尽くした場合、このゲームは先手が必敗、後手が必勝となるようです。

Grundy数の重要な性質として、

0から0に遷移することはできない
0以外からは必ず0に遷移できる

というものがあります

必勝状態なのに相手に負け状態を回せなかったらまずいし、逆もそうなのでたしかにそれはそうですね。

具体的も試したところで、NIMのお話に戻りましょう。

$n = 1$ のとき、Grundy数を求めてみると

石の数	0	1	2	3	4	5	6	7	8	9	10
Grundy数	0	1	2	3	4	5	6	7	8	9	10

ということで、石が残ってれば勝てるということです。それはさっきやりましたね。

$n = 2$ ではどうでしょう。

$(2,3)$ からの遷移を考えてみましょう

$(2,3)$ から遷移できるのは、

左の山を取った場合の $(1,3)$ , $(0,3)$
右の山を取った場合の $(2,2)$ , $(2,1)$ , $(2,0)$

の五通りです

それぞれのGrundy数をさらに求めてみると

状態	Grundy数
$(1,3)$	2
$(0,3)$	3
$(2,2)$	0
$(2,1)$	3
$(2,0)$	2

ということで、 $(2,3)$ のGrundy数は1です（頭の中で計算したので違うかも ...）

何通りか頑張ってみると、石の数が同じだと負けるということがわかると思います。

$n \ge 3$ ではどうなるでしょうか

ここで、なぜかxorという考え方がでてきます。*2

0 も二つの同じ数字も、xorが 0 ですね？つまり、石の数のxorを計算した値が 0 のとき、Grundy数も 0 になるのではないでしょうかということが考えられます（）

そして、実際それは証明できたりします。

ここで大事な点は二つです

xorが 0 になる場合、そこからxorが0になるような状態に遷移することができない
そうでない場合、必ずxorが 0 になるような状態に遷移することができる

さきほど言った、Grundy数の性質ですね。

この二つを満たしていれば、xorが 0 になるような状態で回ってきたら負け（=xorを取ることで、最初から勝敗がわかる）と言えそうです

それでは証明です。

まず、

xorが 0 になる場合、そこからxorが 0 になるような状態に遷移することができない

の方を考えてみましょう

xorが 0 になるということは、それぞれの山の石の数を二進法で考えたとき、各桁の 1 の数が全て偶数ということです。
そのような状態から一つだけ山を選んで石を取り除いた時、どうしてもどこかしらは奇数になってしまいますね。したがって、xorが 0 になる場合、そこからxorが0になるような状態に遷移することができないということです。*3

次に、