第2問

100\times100

の盤を考え、行

a

列

b

（

1\le a,b\le100

）のマスを順序対

(a,b)

と同一視する。

k

を

51\le k\le99

を満たす整数とする。

k

-ナイトとは、縦または横に1マス、もう一方の向きに

k

マス動く駒である。すなわち

(a,b)

から

(c,d)

へ動くとき

(|a-c|,|b-d|)

は

(1,k)

または

(k,1)

のいずれかである。

k

-ナイトはマス

(1,1)

から出発し、何回か手を指す。手の列とは、

(x_0,y_0)=(1,1),(x_1,y_1),\ldots,(x_n,y_n)

という一連のマスであって、すべての

i=1,2,\ldots,n

について

1\le x_i,y_i\le100

かつ

k

-ナイトが

(x_{i-1},y_{i-1})

から

(x_i,y_i)

へ動けるものをいう。このとき各マス

(x_i,y_i)

は到達可能であるという。各

k

について、到達可能なマスの個数

L(k)

を求めよ。

ステップ 3/5: 2手でマスを2だけずらす

前のステップ次のステップ

(x,y)\to(x\pm k,y-1)\to(x,y-2)

詳しい解説

$S$ の外にあるマス $(x,y)$ と $(x,y-2)$ に対し、2手の経路 $(x,y)\to(x+k,y-1)\to(x,y-2)$ または $(x,y)\to(x-k,y-1)\to(x,y-2)$ のいずれかが盤内に収まる。なぜなら $x\le100-k$ または $x\ge k+1$ により $k$ の跳躍の符号を選べるからである。対称的に、 $(x,y)$ と $(x-2,y)$ も座標の役割を入れ替えた2手の経路で結ばれる。