第2题

设

n\ge2

为整数。考虑由

n^2

个单位方格组成的

n\times n

棋盘。若棋盘上

n

个车的摆放使得每行每列恰有一个车,则称这种摆放是和平的。求最大的正整数

k

,使得对

n

个车的每一种和平摆放,都存在一个

k\times k

的正方形,其

k^2

个单位方格中都没有车。

第 3/5 步：下界:n = ℓ² 时的显式和平摆放

上一步下一步

n = \ell^2 : \text{rook at } (r,c),\ r=p\ell+q \implies c \equiv q\ell+p \pmod{\ell^2}

详细分析

当 $n=\ell^2$ 时,将行、列均编号为 $0,\ldots,\ell^2-1$ ,写出 $r=p\ell+q$ (其中 $0\le p,q<\ell$ ),把行 $r$ 的车放在列 $q\ell+p$ ;这样每列恰好被使用一次。可以验证每个 $\ell\times\ell$ 的正方形都会碰到其中一个位置:对于从行 $p\ell+q$ 开始的连续 $\ell$ 行,被占据的列排序后,相邻间隔不超过 $\ell$ ,起始值不超过 $\ell-1$ ,因此任何连续 $\ell$ 列组成的区块都会捕获其中一个。