Grundy数のおはなし(後編)
これは AMC2023 (Adventure Math Calendar2023)の5日目の記事です．4日目までの記事、とても面白いので読みましょう(読みましょう)
前編
では，不偏ゲームの勝敗を判定する方法や，Grundy数についてざーっと紹介しました．この記事では，こういったものがどのように問題に適用できるのかを見ていきたいと思います．
今回紹介する$2$問はちょっと難しめです... 解法を理解するというよりは｢そんな使い方できるんだー｣程度に思ってもらえればいいと思います． 自分がうまく説明できる自信もないので
4. OMC133(E) $700$点問題
無数にある白紙のカードを使って，あなたはOMC君と次のゲームを行います．
【ルール】まず，ゲームマスターが次の一連の操作を$5000$回続けて行う．
- $1$以上$149$以下の整数のうち$1$つを任意に選ぶ．
これが$i$回目$(i=1,2,\ldots,5000)$の操作のとき，選ばれた数を$s_i$とする． - 白紙のカードを$1$枚とり，そこに$s_i$を書き込む．
ただし，ゲームマスターはゲームの進行に中立な存在である．
その後，あなたとOMC君は交互に次の一連の操作を行う．OMC君が先攻である．
- $2$以上の整数が書かれたカードを$1$枚選び，白紙に戻す．このとき書かれていた数を$x$とおく．
- 次をともにみたす正整数$y,z$を選ぶ．$$\gcd(y,z) \neq 1, y+z=x$$
- 白紙のカードを$2$枚とり，それぞれに$y,z$を書き込む．
先に操作を行えなくなった方が$\textbf{負け}$であり，もう一方が勝ちである．
両者が自身の勝ちのために最適に行動します．このとき，ゲームは有限回の操作で終了し，組$(s_1,s_2,\ldots,s_{5000})$ごとにあなたとOMC君のいずれが最終的に勝つかが定まります．$149^{5000}$通りある組のうち，あなたが最終的に勝つものは$M$通りあります．
$M$を$4999$で割った余りを求めて下さい．
例を出すと
$$(2,3,4,4,6)→(2,3,2,2,4,6)→(2,3,2,2,2,2,6)→(2,3,2,2,2,2,3,3)$$
というような感じです． 楽しそう
さて，まずこの問題は不偏ゲームです．なので漸化式かGrundy数を使いたいです．でも漸化式で解くのはとてつもない計算になるので，きっとGrundy数が使えるんだろうなと考えます．
では，この問題において｢$1$つ分のゲーム｣はどれにしたら良いでしょうか．実は初期状態でのカード$1$枚分を$1$つ分にすると，(それらは関わりがないので)それらのGrundy数の排他的論理和で求めることができて，めでたしめでたしです．
以下では
$G(n)=n$のカード$1$枚がある状態でのGrundy数
と定義します．
Grundy数の計算
ここが本質です．(え？) まず，$G(1)=G(2)=0$となります．(操作できない状態は$0$にすることに気を付けて)実験をすると，
$$G(3)=0, G(4)=\mathrm{mex}(g(\{2,2\}))=1, G(5)=0, G(6)=\mathrm{mex}(g(\{2,4\}),g(\{3,3\}),g(\{4,2\}))=2, G(7)=0, G(8)=\mathrm{mex}(g(\{2,6\}),g(\{4,4\}),g(\{6,2\}))=1,\ldots$$
($g(\{y,z\})=G(y) \oplus G(z)$が成り立つことに気を付けます)
ここから次のように推測できます．
- $x$が$6$以上で$4$で割った余りが$2$なら$g(x)=2$？
- $x$が$4$の倍数なら$g(x)=1$？
- $x$が$2$または奇数なら$g(x)=0$？
これは実際に$g(\{y,z\})=G(y) \oplus G(z)$を使うと示すことができます．これを書くと公式解説の丸写しになってしまうので書きたくない 公式解説を見て下さい(人任せ)
最後に$g(最初の状態)=G(s_1) \oplus G(s_2) \oplus \cdots \oplus G(s_{5000})$だったので，$s_1,s_2,\ldots,s_{5000}$の中に$4$の倍数も，$6$以上の$4$で割って$2$余る数も偶数個含まれていればよく，この個数を求めると答えが出ます．
個数を求めるのは割と容易なのでスキップします．(ここが気になる人は｢母関数｣などでぐぐると分かりやすい記事がたくさんあります)
5. OMC051(F) $700$点問題
$S = \{0, 1, 2, \ldots, 10^{2021}-1\}$とし，$S$の空でない部分集合$\{a_1, a_2, \ldots, a_n\}$に対しそのスコアを以下で定めます： $$2^{a_1} + 2^{a_2} + \cdots + 2^{a_n}$$
以下の条件をみたす$S$の部分集合$X$であって，そのスコアが最大になるものは一意に存在することが保証されます．その元の個数を素数$1009$で割った余りを求めてください．
- 任意の$a,b \in X$に対して，$a,b$の十進法表記で各桁を比較すると，ちょうど$2020$ヵ所が一致することはない．
ただし，上の条件において$a,b$が十進法表記で$2021$桁に満たない場合は，例えば$1$ならば$000 \cdots 001$のように，先頭に$0$を適当に補うことで$2021$桁の数とみなして考えるものとします．
$334$・$335$のように，ちょうど$1$桁が違うようなものが存在しないようにスコアを大きくするとき，要素数はいくつ？という問題です．
スコアの最大化は$X$の要素を大きい順に選んでいけば良い($2^n \gt 2^{n-1}+2^{n-2}+ \cdots + 2^0$なので)ですが，以下では$\textbf{小さい順}$で考えていきます．このように考えても$10^{2021}-1-(Xの要素)$とすれば大小関係がひっくり返るので，問題ありません．
さて，この問題はゲームとは縁が無さそうですが，実は次のようなゲームを考えるとうまくいきます．
$2021$個の山があり，$i$個目の山には$a_i(\leq 9)$個の石が積まれている．先手・後手はここから｢$1$つの山を選び，そこから$1$個以上の石をとる｣という操作を交互に行う．自分の番で石を$0$個にしたら$\textbf{勝ち}$である．
両者が最適に行動するとき，どちらが勝つか？
これを解くのはGrundy数を使えば良いです．$a_i$個石が積まれた$1$つの山について，そのGrundy数は$a_i$だと分かります．よって，$a_1 \oplus a_2 \oplus \cdots \oplus a_{2021} \geq 1$なら先手必勝，そうでないなら後手必勝となります．
今度は漸化式を使ってみます．$2021$を$3$に変えて数が小さいところから求めていきます．
$$f(0,0,0)=0, f(0,0,1)=\overline{f(0,0,0)}=1, f(1,1,0)=\overline{f(1,0,0) ~ \& ~ f(0,1,0)}=0, f(0,0,2)=\overline{f(0,0,1) ~ \& ~ f(0,0,0)}=1$$
...漸化式は｢遷移できる状態が全て$1$なら$0$，$0$があるなら$1$｣でした．これって元の問題と似ていませんか？
例えば，$110$を集合$X$に入れるには，$100,010$の$2$つが$X$に含まれていないようにしなければなりません．つまり，遷移できる状態の数が全て｢含まれていない→$\mathbf{1}$の状態｣ならその数を入れて，遷移できる状態の数に｢含まれている→$\mathbf{0}$の状態｣があるならその数を除かなければいけません．よって，このゲームを解くことは元の問題を解くことと同じになります！
(大小関係を逆にした上で)ある要素が$X$に含まれる$\iff$上のゲームにおいて後手必勝$\iff$$a_1 \oplus a_2 \oplus \cdots \oplus a_{2021}=0$
なので，上の第$3$辺を満たす個数を求めれば良いです．(ちなみに個数には影響しませんが，大小関係を元に戻すと$(9-a_1) \oplus (9-a_2) \oplus \cdots \oplus (9-a_{2021})=0$になります) 個数求めパートは""本質に比べれば""容易なのでここでもスキップします．
おわりに
前後編に分けた長い記事になりましたが，なんとか書ききれて良かったです．みんなでGrundy数を攻略しまくって不偏ゲームの問題が出なくなるようにしてやりましょう！
ここまで読んで頂きありがとうございました～！