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) を求めよ。
ステップ 1/5: マスが合法手を持つのはいつか
(x,y) has a legal move  ⟺  x≤100−k∨x≥k+1∨y≤100−k∨y≥k+1(x,y)\text{ has a legal move}\iff x\le100-k\lor x\ge k+1\lor y\le100-k\lor y\ge k+1
詳しい解説

kk-ナイトの手は一方の座標を ±1\pm1、他方を ±k\pm k だけ変える。±1\pm1 の部分は、すでに [1,100][1,100] にある座標がその範囲内に留まるように符号を選べる。したがって (x,y)(x,y) が盤内の手を少なくとも1つ持つのは、kk の部分を xx か yy に適用できるとき、すなわち x≤100−kx\le100-k または x≥k+1x\ge k+1 または y≤100−ky\le100-k または y≥k+1y\ge k+1 のときに限る。すべての手は可逆なので、同じ条件が (x,y)(x,y) に盤内の手(入るか出るかを問わず)が存在するかどうかを決める。