MathLabs

第2题

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

答案是 k=⌊n−1⌋k=\lfloor\sqrt{n-1}\rfloor。证明方法是对每个正整数 ℓ\ell 分别证明:(i) 若 n>ℓ2n>\ell^2,则每种和平摆放都存在一个空的 ℓ×ℓ\ell\times\ell 正方形;(ii) 若 n≤ℓ2n\le\ell^2,则存在一种和平摆放没有这样的正方形;两者结合即可确定满足条件的最大 ℓ\ell 为 ⌊n−1⌋\lfloor\sqrt{n-1}\rfloor。