MathLabs

第2問

n≥2n\ge2 を整数とする。n2n^2 個の単位正方形からなる n×nn\times n のチェス盤を考える。この盤上の nn 個のルークの配置が平和的であるとは、どの行にもどの列にもちょうど1個のルークがあることをいう。nn 個のルークのどの平和的な配置に対しても、その k2k^2 個の単位正方形のいずれにもルークが置かれていない k×kk\times k の正方形が存在するような、最大の正の整数 kk を求めよ。
ステップ 4/5: 下界:n < ℓ² への拡張
前のステップ次のステップ
n<ℓ2:trim rows/columns, then re-pair empty onesn < \ell^2 : \text{trim rows/columns, then re-pair empty ones}
詳しい解説

n<ℓ2n<\ell^2 のとき、上の ℓ2\ell^2 に対する構成から出発し、下から ℓ2−n\ell^2-n 行と、最も右の ℓ2−n\ell^2-n 列を削除する。この削除によって空の ℓ×ℓ\ell\times\ell 正方形は生じないが、残った行や列の中にはルークがなくなるものが出てくることがある。空の行の個数と空の列の個数は等しいので、それらを任意にペアにし、各ペア(空の行、空の列)の交点にルークを置くことで、空の ℓ×ℓ\ell\times\ell 正方形を持たない nn 個のルークの平和的な配置が復元される。