第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)

を求めよ。

ステップ 4/5: S の外では色ごとに1つの連結成分

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

x+y\equiv1\!\!\pmod2\implies(x,y)\text{ joined to }(1,1)\text{ outside }S

詳しい解説

前の段階のずらしを繰り返すことで、 $S$ の外にある任意のマスは、 $x+y$ の偶奇が同じである $S$ の外の任意の別のマスと、2手の経路の連鎖で結ばれる。なぜなら各2手の経路は $x+y$ を偶数量 $\pm2$ または $\pm2k$ だけ変えるからである。したがって $(1,1)$ と同じ色、すなわち $x+y$ が偶数である $S$ の外のマスはすべて $(1,1)$ を含む1つの連結成分に属する。