第2問

n\ge2

を整数とする。

n^2

個の単位正方形からなる

n\times n

のチェス盤を考える。この盤上の

n

個のルークの配置が平和的であるとは、どの行にもどの列にもちょうど1個のルークがあることをいう。

n

個のルークのどの平和的な配置に対しても、その

k^2

個の単位正方形のいずれにもルークが置かれていない

k\times k

の正方形が存在するような、最大の正の整数

k

を求めよ。

ステップ 3/5: 下界:n = ℓ² のための具体的な平和的配置

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

n = \ell^2 : \text{rook at } (r,c),\ r=p\ell+q \implies c \equiv q\ell+p \pmod{\ell^2}

詳しい解説

$n=\ell^2$ のとき、行と列を $0,\ldots,\ell^2-1$ と番号付けし、行 $r=p\ell+q$ ( $0\le p,q<\ell$ )に対して行 $r$ のルークを列 $q\ell+p$ に置く。これにより各列がちょうど1回使われる。すべての $\ell\times\ell$ 正方形がこれらの位置のいずれかと出会うことが確かめられる:行 $p\ell+q$ から始まる連続する $\ell$ 行に対して、占有された列を並べ替えると、増分は高々 $\ell$ で、最初の値は高々 $\ell-1$ であるため、任意の連続する $\ell$ 列のブロックはそのうちの1つを捉える。