MathLabs

第2题

设 n≥2n\ge2 为整数。考虑由 n2n^2 个单位方格组成的 n×nn\times n 棋盘。若棋盘上 nn 个车的摆放使得每行每列恰有一个车,则称这种摆放是和平的。求最大的正整数 kk,使得对 nn 个车的每一种和平摆放,都存在一个 k×kk\times k 的正方形,其 k2k^2 个单位方格中都没有车。
第 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,设 UU 为包含 RR 在内的连续 ℓ\ell 行的并集;UU 恰含 ℓ\ell 个车。从 UU 中去掉最左边的 n−ℓ2≥1n-\ell^2\ge1 列(至少去掉 RR 中的车),剩下一个 ℓ2×ℓ\ell^2\times\ell 的矩形,其中至多含 ℓ−1\ell-1 个车,可分成 ℓ\ell 个 ℓ×ℓ\ell\times\ell 的正方形;由鸽笼原理,其中必有一个是空的。