MathLabs

第2题

设 n≥2n\ge2 为整数。考虑由 n2n^2 个单位方格组成的 n×nn\times n 棋盘。若棋盘上 nn 个车的摆放使得每行每列恰有一个车,则称这种摆放是和平的。求最大的正整数 kk,使得对 nn 个车的每一种和平摆放,都存在一个 k×kk\times k 的正方形,其 k2k^2 个单位方格中都没有车。
第 5/5 步：结论
上一步下一步
k=⌊n−1⌋=max⁡{ℓ:ℓ2<n}k = \left\lfloor \sqrt{n-1} \right\rfloor = \max\{\ell : \ell^2 < n\}
详细分析

综合两部分:ℓ\ell 对每种和平摆放都有效当且仅当 ℓ2<n\ell^2<n;而当 ℓ2≥n\ell^2\ge n 时不能保证。满足条件的最大 ℓ\ell 即为满足 ℓ2<n\ell^2<n(即 ℓ2≤n−1\ell^2\le n-1)的最大整数,也就是 ℓ=⌊n−1⌋\ell=\lfloor\sqrt{n-1}\rfloor;这就是所求的 kk 值。