ARC091 問題F: Strange Nim の平易な解説 _2
の続き。
前回まで
- 全てのImpartial gameは、Grundy数を導ければ、そのGrundy数に相当するNimに帰結できる。
- Nimは、（xor演算を応用することで）初期条件からとても簡単に先後どちらの必勝かが分かる。
- よって全てのImpartial gameは、Grundy数を調べることで簡単に解くことができる。
問題のゲームはImpartialなので、そのゲームにおけるGrundy数を導ければよかった。
Grundy数のおさらい
ある状態にあるゲームのGrundy数は、
「可能な遷移先全てのGrundy数と異なる整数のうち、最小のもの」である。
可能な遷移先に0があれば、絶対に0にはならない。
また、0がなければ、必ず0になる。
これを念頭に置いて、解説を再び読んでいく。
Grundy数の構成
解説では、いきなりGrundy数の構成の仕方を示している。
これが成り立つことを、帰納法を用いて証明している。
証明は非常に混み入っていてぱっと見で理解するのはとても難しい。そこで、K=4の時の具体例を調べてみた。以下では、山(N, K)のGrundy数をg(N, K)とし、gでGrundy数を表す。
N<4の時は、一つも石が取れないので、g=0
N=4の時、遷移先はg(3, 4)=0のみ。よってg(4, 4)=1
N=5：遷移先はg(4, 4)=1のみで、g(5, 4)=0
N=6：遷移先はg(5, 4)=0のみで、g(6, 4)=1
N=7：遷移先はg(6, 4)=1のみで、g(7, 4)=0
N=8：遷移先はg(7, 4)=0, g(6, 4)=1なので、これらに一致しない最小の整数g(8, 4)=2
N=9：遷移先はg(8, 4)=2, g(7, 4)=0なので、これらに一致しない最小の整数g(9, 4)=1
N=10：遷移先はg(9, 4)=1, g(8, 4)=2なので、これらに一致しない最小の整数g(10, 4)=0
N=11：遷移先はg(10, 4)=0, g(9, 4)=1なので、これらに一致しない最小の整数g(11, 4)=2
N=12：遷移先はg(11, 4)=2, g(10, 4)=0, g(9, 4)=1なので、これらに一致しない最小の整数g(11, 4)=3
...
と調べていくと、N<=47では、
| N | K | mod(N, K) | ⌊N/K⌋ | N − ⌊N/K⌋ − 1 | G(N, K) |
| 1 | 4 | 1 | 0 | 0 | 0 |
| 2 | 4 | 2 | 0 | 1 | 0 |
| 3 | 4 | 3 | 0 | 2 | 0 |
| 4 | 4 | 0 | 1 | 2 | 1 |
| 5 | 4 | 1 | 1 | 3 | 0 |
| 6 | 4 | 2 | 1 | 4 | 1 |
| 7 | 4 | 3 | 1 | 5 | 0 |
| 8 | 4 | 0 | 2 | 5 | 2 |
| 9 | 4 | 1 | 2 | 6 | 1 |
| 10 | 4 | 2 | 2 | 7 | 0 |
| 11 | 4 | 3 | 2 | 8 | 2 |
| 12 | 4 | 0 | 3 | 8 | 3 |
| 13 | 4 | 1 | 3 | 9 | 1 |
| 14 | 4 | 2 | 3 | 10 | 0 |
| 15 | 4 | 3 | 3 | 11 | 2 |
| 16 | 4 | 0 | 4 | 11 | 4 |
| 17 | 4 | 1 | 4 | 12 | 3 |
| 18 | 4 | 2 | 4 | 13 | 1 |
| 19 | 4 | 3 | 4 | 14 | 0 |
| 20 | 4 | 0 | 5 | 14 | 5 |
| 21 | 4 | 1 | 5 | 15 | 2 |
| 22 | 4 | 2 | 5 | 16 | 4 |
| 23 | 4 | 3 | 5 | 17 | 3 |
| 24 | 4 | 0 | 6 | 17 | 6 |
| 25 | 4 | 1 | 6 | 18 | 1 |
| 26 | 4 | 2 | 6 | 19 | 0 |
| 27 | 4 | 3 | 6 | 20 | 5 |
| 28 | 4 | 0 | 7 | 20 | 7 |
| 29 | 4 | 1 | 7 | 21 | 2 |
| 30 | 4 | 2 | 7 | 22 | 4 |
| 31 | 4 | 3 | 7 | 23 | 3 |
| 32 | 4 | 0 | 8 | 23 | 8 |
| 33 | 4 | 1 | 8 | 24 | 6 |
| 34 | 4 | 2 | 8 | 25 | 1 |
| 35 | 4 | 3 | 8 | 26 | 0 |
| 36 | 4 | 0 | 9 | 26 | 9 |
| 37 | 4 | 1 | 9 | 27 | 5 |
| 38 | 4 | 2 | 9 | 28 | 7 |
| 39 | 4 | 3 | 9 | 29 | 2 |
| 40 | 4 | 0 | 10 | 29 | 10 |
| 41 | 4 | 1 | 10 | 30 | 4 |
| 42 | 4 | 2 | 10 | 31 | 3 |
| 43 | 4 | 3 | 10 | 32 | 8 |
| 44 | 4 | 0 | 11 | 32 | 11 |
| 45 | 4 | 1 | 11 | 33 | 6 |
| 46 | 4 | 2 | 11 | 34 | 1 |
| 47 | 4 | 3 | 11 | 35 | 0 |
表をみてパッとわかることを列挙してみる。
- 0と0の間の距離（0-0区間）が徐々に伸びている。
- 0-0区間の間の数字は、1からある整数までの全ての整数を網羅している。
- mod(N, K)が0（NがKの倍数）の時のgの値は、一つ前の0-0区間にはないgの値にになっている。mod(N, K)=0が複数ある場合は、下から小さい順に新たなgが入る。
- 0-0区間の間の数字の順番は、一つ前の0-0区間にある数字の順番を入れ替えないようになっている。その数字の間に新たなgが入っていく。
1.は、Nが増えるにつれて遷移可能な状態が増えていくことから生まれている。(N, K)から遷移が可能な状態の数は、ゲームの性質上⌊N/K⌋ である。
3.から、mod(N, K) = 0の時をよく見ると、g(N, K) = N/Kとなっていることが分かる。そこで、「mod(N, K) = 0ならば、g(N, K) = N/K」ではないかと類推できる。
そこで、mod(N, K) /=0の時を考えたい。
2. や4. を踏まえて再び表を見る。(i, K)から遷移可能な範囲 i - ⌊i/K⌋ <= N < iから一つ下の、 N = i - ⌊i/K⌋ -1への遷移が、i-1では可能だったのに対して、iではできなくなる。つまり、g(i - ⌊i/K⌋ -1, K)がg(i, K)に引き継がれるだろうと類推できる。よって、
「mod(N, K) /= 0ならば、g(N, K) = g(N - ⌊N/K⌋-1, K)」
このようにして、gの一般形が急に出てきた理由が分かった。
