每日一题[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$．