每日一题[1594]最大距离

求最大的正整数 $n$,将正整数 $1$ 到 $400$ 任意填入 $20\times 20$ 的 $400$ 个方格中,则总有一行或一列,其中两个数之差不小于 $n$.

答案    $209$.

解析    将正方形表格分为 $20\times 10$ 的两个矩形表格,然后将 $1$ 到 $200$ 依次逐行按照从小到大的顺序填入左侧表格,同理将 $201$ 到 $400$ 填入右侧表格,则在此表格中,每行中两数之差不大于 $209$,每列中两数之差不大于 $190$,所以 $n\leqslant 209$. 令 $M=\{1,2,\cdots,91\}$,$N=\{300,301,\cdots,400\}$,易知,若集合 $M,N$ 中各有一个数位于表格的同一行或同一列,则两数之差不小于 $209$,因此只需证明在表格的每一行及每一列中必有集合 $M,N$ 中各一个数. 设表格已经任意填好,表格中共有 $i$ 行 $j$ 列含有 $M$ 中的数,表格中共有 $k$ 行 $l$ 列含有 $N$ 中的数,则\[i+j\geqslant 2\sqrt{ij}\geqslant 2\sqrt{91}>19,\]即 $i+j\geqslant 20$,同理\[k+l\geqslant 2\sqrt{kl}\geqslant 2\sqrt{101}>20,\]因此\[i+j+k+l\geqslant 41,\]利用抽屉原理,必有一行或一列,同时含有两个集合中的各一个数,命题得证. 总上所述,$n=209$.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表回复