MathLabs

第2問

100×100100\times100 の盤を考え、行 aa 列 bb（1≤a,b≤1001\le a,b\le100）のマスを順序対 (a,b)(a,b) と同一視する。kk を 51≤k≤9951\le k\le99 を満たす整数とする。kk-ナイトとは、縦または横に1マス、もう一方の向きに kk マス動く駒である。すなわち (a,b)(a,b) から (c,d)(c,d) へ動くとき (∣a−c∣,∣b−d∣)(|a-c|,|b-d|) は (1,k)(1,k) または (k,1)(k,1) のいずれかである。kk-ナイトはマス (1,1)(1,1) から出発し、何回か手を指す。手の列とは、(x0,y0)=(1,1),(x1,y1),…,(xn,yn)(x_0,y_0)=(1,1),(x_1,y_1),\ldots,(x_n,y_n) という一連のマスであって、すべての i=1,2,…,ni=1,2,\ldots,n について 1≤xi,yi≤1001\le x_i,y_i\le100 かつ kk-ナイトが (xi−1,yi−1)(x_{i-1},y_{i-1}) から (xi,yi)(x_i,y_i) へ動けるものをいう。このとき各マス (xi,yi)(x_i,y_i) は到達可能であるという。各 kk について、到達可能なマスの個数 L(k)L(k) を求めよ。
ステップ 5/5: パリティ不変量が答えを決める
前のステップ次のステップ
L(k)=1002−(2k−100)2 (k even),L(k)=12(1002−(2k−100)2) (k odd)L(k)=100^2-(2k-100)^2\ (k\text{ even}),\qquad L(k)=\tfrac12\big(100^2-(2k-100)^2\big)\ (k\text{ odd})
詳しい解説

1回の kk-ナイトの手は x+yx+y を ±(k−1)\pm(k-1) または ±(k+1)\pm(k+1) だけ変え、どちらも k+1k+1 と同じ偶奇を持つ。kk が奇数なら k+1k+1 は偶数なので x+y mod 2x+y\bmod2 は不変量であり、(1,1)(1,1) と同じ色を持つ SS の外の (1002−(2k−100)2)/2\big(100^2-(2k-100)^2\big)/2 個のマスのみが到達可能である。kk が偶数なら k+1k+1 は奇数なので、1回の手ですでに反対の色のマスに到達でき、その色に前の段階を適用すると SS の外の残りのマスもすべて到達可能であることが分かる。したがって SS の外の 1002−(2k−100)2100^2-(2k-100)^2 個のマスすべてが到達可能である。