２山nimのgrundy数

grundy.txt

xの山とyの山のgrundy数を(x,y)に書いた表を考える。

1*1の表：
|0|
0-indexedなので、両方0の山です。

2*2の表：
|01|
|10|
このパターンが基本になってきます。

4*4の表：
|0123|
|1032|
|2301|
|3210|
2*2のブロックが2*2個並んでいる、と見てください。
まだ小さくて説明しにくいので次に行きます。

8*8の表：
|0123|4567|
|1032|5476|
|2301|6745|
|3210|7654|
|---------|
|4567|0123|
|5476|1032|
|6745|2301|
|7654|3210|
4*4のブロックが2*2個並んでいる、と見てください。
ここで重要なのが、4*4の表をみると「どの行もどの列も0~3が1つずつある」という点で、
つまり8*8の右上と左下のブロックは4以上の数しか入らないことになります。
さらに、右上と左下のブロックでは「どのマスも4以上しか入らない」という条件以外は4*4の表と同じ条件になっているので、4*4の表の各要素に4を足したような表になります。
右下のブロックについては、上にも左にも3以下の数がないので、4*4の表と同じように埋まります。

表の１辺を２倍２倍にしていくと表が作れて、これは実はxorの表と同じものになっていました、という話。