每日一题[1283]无处容身

设集合 $A=\{1,2,3,\cdots,2018\}$,对于 $A$ 的 $1009$ 元子集 $M$,若存在 $a,b\in M$ 满足 $a\mid b$,则称 $M$ 为好集.求最大的正整数 $n$,使得所有 $A$ 的包含 $n$ 的 $1009$ 元子集都是好集.

答案    $671$.

解析    将 $A$ 中的 $2018$ 个数按最大奇因数划分为 $1009$ 个集合:\[\begin{split} A_1&=\{1,2,4,\cdots,2^{10}\},\\ A_3&=\{3,6,12,\cdots,3\cdot 2^{9}\},\\ &\cdots,\\ A_{2017}&=\{2017\},\end{split}\] 若 $A$ 的 $1009$ 元子集 $M$ 包含这些分划中某个集合的两个元素,那么 $M$ 即为好集.接下来考虑 $M$ 中的元素分别来自这 $1009$ 个集合的情形,此时必然有\[1011,1013,\cdots,2017\in M,\]于是当 $n$ 可以整除这些数之一时,必然有包含 $n$ 的 $1009$ 元子集是好集,考虑到\[2013=3\cdot 671,\]于是 $n$ 可以取 $671$.接下来证明 $n$ 不可能取 $672$. [[case]]情形一[[/case]] $n\geqslant 1009$.此时取\[M=\{1009,1010,\cdots,2017\}\]就得到了不是好集的 $1009$ 元子集. [[case]]情形二[[/case]] $672\leqslant n\leqslant 1008$.取\[P=\{672,673,\cdots,1008\},\]且\[Q=\{1009,1010,\cdots,2017\}\backslash \{ 2t\mid t\in P\},\]则\[M=P\cup Q\]即为不是好集的 $1009$ 元子集.这是因为,若 $x,kx\in M$($k,x\in\mathbb N^{\ast}$,$x\geqslant 672$,$k\geqslant 2$),则 $k$ 只可能为 $2$ 或 $3$,容易验证均不可能. 综上所述,最大正整数 $n$ 的值为 $672$.

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

发表评论