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) を求めよ。
ステップ 2/5: 手を持たない中央の正方形
S={(x,y):101−k≤x,y≤k},∣S∣=(2k−100)2S=\{(x,y):101-k\le x,y\le k\},\qquad|S|=(2k-100)^2
詳しい解説

前の段階の条件を否定すると、マス (x,y)(x,y) がまったく合法手を持たないのは、ちょうど 101−k≤x≤k101-k\le x\le k かつ 101−k≤y≤k101-k\le y\le k のときである。これは一辺 k−(101−k)+1=2k−100k-(101-k)+1=2k-100 の正方形 SS であり、∣S∣=(2k−100)2|S|=(2k-100)^2 となる。SS 内のマスは孤立しており、残りの 1002−(2k−100)2100^2-(2k-100)^2 個のマスはそれぞれ少なくとも1つの手を持つ。k≤99k\le99 のとき 101−k≥2101-k\ge2 なので、出発マス (1,1)(1,1) は決して SS に属さない。