その１はこちら
【問題】1次元のマス目（1xN）に交互にドミノ（1x2）を置いて行って置けなくなった方が負けというゲームで、先手が必ず負けになるN<100をリストせよ。
この問題をGrundy数を使ってN＝7までの結果の再び表にします。
| N | mex | Grundy数 |
|---|---|---|
| N=0 | 0 | |
| N=1 | 0 | |
| N=2 | $mex(G(0))$ | 1 |
| N=3 | $mex(G(1))$ | 1 |
| N=4 | $mex(G(1),G(2))=mex(0,1)$ | 2 |
| N=5 | $mex(G(3),G(1)\oplus G(2))=mex(1,1)$ | 0 |
| N=6 | $mex(G(4),G(1)\oplus G(3),G(2)\oplus G(2))=mex(2,1,0)$ | 3 |
| N=7 | $mex(G(5),G(1)\oplus G(4),G(2)\oplus G(3))=mex(0,2,0)$ | 1 |
これから推測されるように、任意のNの時のGrundy数は以下の式で表せます。
- $G(N) = mex(\\ G(0)\oplus G(N-2),\\ G(1)\oplus G(N-2-1),\\ ...\\ G(k)\oplus G(N-2-k))$
ここで$0\leqq k \leqq floor(N/2)$
これをそのままPythonのプログラムにします。まずmex関数を定義します。単純に0からリストの最大値まで見ていって、ない数があったらそれを返し、もし全部あった場合は最大値+1を返します。
def mex(gl):
for i in range(max(gl)+2):
if i not in gl: return i
return ("error")
これを使って$G(N)$の計算を行います。2つ前までのGrundy数のリストを逆順にしてXORを取り、mexを見つけてGrundy数のリストに加えるのを繰り返せばOKです。
(XORを取るのは半分までで良いのですがコードを簡単にするために全部取っています)
import numpy as np
n = 100
GL = np.array([0, 0]) # G(0), G(1)
for i in range(2, n+1):
GL = np.append(GL, mex(GL[:-1]^GL[-2::-1]))
print(list(*np.where(GL==0)))
# [0, 1, 5, 9, 15, 21, 25, 29, 35, 39, 43, 55, 59, 63, 73, 77, 89, 93, 97]
これでオンライン整数列大辞典に掲載されていた数列のN<100が計算できました。