MathLabs

第2题

设 n≥2n\ge2 为整数。考虑由 n2n^2 个单位方格组成的 n×nn\times n 棋盘。若棋盘上 nn 个车的摆放使得每行每列恰有一个车,则称这种摆放是和平的。求最大的正整数 kk,使得对 nn 个车的每一种和平摆放,都存在一个 k×kk\times k 的正方形,其 k2k^2 个单位方格中都没有车。
第 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 正方形,但剩下的某些行、列可能变得没有车;由于空行数与空列数相等,把它们任意配对,并在每对(空行、空列)的交点处放一个车,即可恢复一个含 nn 个车、且没有空 ℓ×ℓ\ell\times\ell 正方形的和平摆放。