Grundy数のおはなし(前編)

　これは AMC2023 (Advent Math Calender 2023)の1日目の記事です．2日目以降の担当の方々はとても素晴らしい記事を書かれている(断定)ので，そちらの方も是非～！

0. 導入

　今回は主に(というか全て)ゲーム理論についてのお話です．きっと後編の応用を見たら面白いと思ってもらえるんじゃないかなと思います．
　あと，これを追記して欲しいというのがあれば教えて下さい！　私が宿題をする時間を削って書きます

1. 不偏ゲーム？

　今回の本題になっているGrundy数は，$\textbf{不偏ゲーム}$と呼ばれるゲームに適用することができます．では，不偏ゲームとは何なのでしょうか．ざっくり言うと "2人でして、運が関係なく、平等なゲーム" です．厳密には

を全て満たすものをいうそうです．

　不偏ゲーム(に限らず運に左右されないゲーム)は$2$人が最適な手を選べば，必ずどっちが勝つか決まります．

2. 漸化式

　ここからが本題です．

　実は全ての不偏ゲームは，漸化式(dp)によってどっちが勝てるか判定することができます．(！)　次のようなゲームを考えてみます．

　これを漸化式で解いてみます．
$$A_i ~ (i=0,1,\ldots) ~ = ~ (自分から石がi個の状態から始めるとき，自分必勝か相手必勝か)$$
(つまり，自分を先手として自分が勝つか相手が勝つか)と定めます．

　まず，最初の項が分からないと何もできないので$A_0$を求めます．これはあれですが，便宜上$A_0=\textbf{相手必勝}$とします．(一般に，操作できなくなった状態は後手必勝とした方が都合が良いです)

　次に$A_1$を考えてみます．{石が$1$つだけ残った状態} から自分が$1$つ石をとると ｢相手のターンで{石が$0$個残った状態}｣ になります．つまり相手にとって$A_0=$相手必勝 なので，$A_1=\textbf{自分必勝}$ということが分かります．

　次に次に，$A_2$を考えます．{石が$2$つだけ残った状態} からは次の$2$つの場合に分けられます．

①自分が石を$1$個とると {石が$1$つだけ残った状態}　→　相手にとって$A_1=$自分必勝　 つまり 相手必勝
②自分が石を$2$個とると {石が$0$つだけ残った状態}　→　相手にとって$A_0=$相手必勝　 つまり 自分必勝

　どっちを選ぶのとなりますが，｢自分｣は常に勝つために動くので，無言で自分必勝の方(②)を選びます．したがって$A_2=\textbf{自分必勝}$です．

　同様に$A_3$もすると，

①自分が石を$1$個とると {石が$2$つだけ残った状態}　→　相手にとって$A_2=$自分必勝　 つまり 相手必勝
②自分が石を$2$個とると {石が$1$つだけ残った状態}　→　相手にとって$A_1=$自分必勝　 つまり 相手必勝

　これは、｢自分｣はどう頑張っても相手必勝になってしまいました．(悔しい)　つまりこの場合は$A_3=\textbf{相手必勝}$です．

　...という風に計算していくと，$A_{3m+1},A_{3m+2}$のとき自分必勝，$A_{3m}$のとき相手必勝となることが帰納的に分かります．なので答えは

　$n=3m+1,3m+2$のとき先手必勝，$n=3m$のとき後手必勝 ($m$は整数)

となります．

　上で言ったことを一般化すると次のようになります．やっと数学っぽいことが書ける

　これを使ってもう$1$問不偏ゲームの問題を解いてみましょう．

※上が伝わりにくいと思うので例を出すと，

先｢$1,2$｣　後｢$3,4,5$｣　先｢$6$｣　後｢$7,8,9$｣ ...

のような感じです．　地味

　上の命題を使います！
　
$f(n)=$本問題の$1$から$n$までの整数で$n$を言ったら勝ちの場合で，先手必勝なら$1$，後手必勝なら$0$
　
とします．
　まず，便宜上$f(0)=0$とします．そこから次のように計算できます．
$$f(1)=\overline{f(0)}=1,　f(2)=\overline{f(0) ~ \& ~ f(1)}=1,　f(3)=\overline{f(0) ~ \& ~ f(1) ~ \& ~ f(2)}=1,　f(4)=\overline{f(1) ~ \& ~ f(2) ~ \& ~ f(3)}=0,　f(5)=\overline{f(2) ~ \& ~ f(3) ~ \& ~ f(4)}=1,　f(6)=\overline{f(3) ~ \& ~ f(4) ~ \& ~ f(5)}=1 \ldots$$
　勘の良い人は気付いたかもしれませんが，実はこれは$0,1,1,1$を繰り返しています．(これは実際に帰納法で示すことができます)　よって，$f(30)=1$なので，先手必勝と分かります．

　これで私たちは不偏ゲームを(理論上)全て判定することができるようになりました．これの上級者向けver(？)が次に紹介する Grundy数 というものです．

3. Grundy数？

　Grundy数は，主に同じ不偏ゲームを同時進行するときに使うことができます(もうちょっと広く使えるかもしれません　怪しい)．次のようなゲームを考えてみます．

　例えば$n=m=7$なら，
$$(7,7)→(7,6)→(7,4)→(6,4)→(6,3)→(4,3)→ \cdots$$
という風に進んでいきます．

　今回なら最初のゲームを$2$つ同時にやっているような感じです．こんなときはGrundy数の出番というわけです．

　Grundy数は同じゲームを同時にするときに使えると言いましたが，このゲームの｢$1$つ分のゲーム｣について定義されます．例えば，先程の 問題$3$ の例なら，問題$1$ が｢$1$つ分のゲーム｣です．
　以下では，ある局面$V$のGrundy数は$g(V)$で表します．

　まず，操作できなくなった状態のGrundy数は$0$とします．
　今，ある局面$V$について，そこから遷移できる局面が$V_1,V_2,\ldots,V_n$だとします．すると，$V$のGrundy数$g(V)$は
$$g(V) = \mathrm{mex}(g(V_1),g(V_2),\ldots,g(V_n))$$で求めることができます．
　ここで，$\mathrm{mex}$とは｢その集合の中に含まれていない最小の非負整数｣と定義されているものです．例えば，$\mathrm{mex}(0,1,3)=2,　\mathrm{mex}(0,1,0,2)=3,　\mathrm{mex}(100,100,200,200)=0$です．

　試しに問題$1$のGrundy数を求めてみましょう．みやすいように，

$G(n)=$石が$n$個のときのGrundy数

とします．
　まず，$G(0)=0$です．そこから，次のように計算できます．
$$G(1)=\mathrm{mex}(G(0))=1,　G(2)=\mathrm{mex}(G(0),G(1))=2,　G(3)=\mathrm{mex}(G(1),G(2))=0,　G(4)=\mathrm{mex}(G(2),G(3))=1,\ldots$$
　勘の良い人はもう気付いたかもしれません(2回目)が，$0,1,2$が繰り返されています．$G(n)$は$n$を$3$で割った余りになっていますね．
　実は，Grundy数は先手必勝なら$1$以上，後手必勝なら$0$になります．

　｢...でこれがどう役に立つんだよ！｣と思った方も多いと思います．なんと次のような偉大な定理が知られています．

　じゃあ証明を...　としたいところですが，難しくてまだ理解できていません...　気が向いたら書こうと思うので，とりあえず今はこの定理を発見した方に感謝しながら食べたいと思います．

　これを問題$3$に使ってみます．$Q_1$は$n$個の山，$Q_2$は$m$個の山とすると，$G(n) \oplus G(m) \geq 1$なら先手必勝，$G(n) \oplus G(m) = 0$なら後手必勝となります！
(この先手必勝の条件は$n-m$が$3$の倍数でないことと同値になっていることも分かりますね．)

つづく...

　後編はこれらを使うOMCの問題$2$問を解説しようと思います．お楽しみに．