MathLabs

第2問

n≥2n\ge2 を整数とする。n2n^2 個の単位正方形からなる n×nn\times n のチェス盤を考える。この盤上の nn 個のルークの配置が平和的であるとは、どの行にもどの列にもちょうど1個のルークがあることをいう。nn 個のルークのどの平和的な配置に対しても、その k2k^2 個の単位正方形のいずれにもルークが置かれていない k×kk\times k の正方形が存在するような、最大の正の整数 kk を求めよ。
ステップ 2/5: 上界:ℓ² × ℓ ブロックへの鳩の巣原理
前のステップ次のステップ
n>ℓ2  ⟹  some ℓ×ℓ square is emptyn > \ell^2 \implies \text{some } \ell\times\ell \text{ square is empty}
詳しい解説

n>ℓ2n>\ell^2 とする。すべての行の中でルークが最も左の列にある行 RR をとり、RR を含む連続する ℓ\ell 個の行の和集合を UU とする。UU にはちょうど ℓ\ell 個のルークがある。UU から最も左の n−ℓ2≥1n-\ell^2\ge1 個の列を除くと(少なくとも RR のルークが除かれる)、ℓ2×ℓ\ell^2\times\ell の長方形が残り、そこには高々 ℓ−1\ell-1 個のルークしかない。これは ℓ×ℓ\ell\times\ell の正方形 ℓ\ell 個に分割できるので、鳩の巣原理によりそのうち1つは空である。