每日一题[1349]疏剪

从 $1,2,\cdots,2018$ 中取 $k$ 个不同的数，其中任意 $2$ 个数的商不等于 $\dfrac 32$，那么 $k$ 的最大值为_______．

答案    $1513$．

解析    任何一个正整数 $n$ 必然可以写成 $a\cdot b$ 的形式，其中 $2\nmid a$ 且 $3\nmid a$，$a,b\in\mathbb N^{\ast}$．此时 $b=2^p\cdot 3^q$，其中 $p,q\in\mathbb N$．所有可能的 $a$ 为 $$1,5,7,11,13,17,19,\cdots,$$ 将所有可能的 $b$ 按对应的 $p+q$ 的大小分成 $10$ 行书写： $$\begin{array}{|cc|cc|cc|c|}\hline 1&&&&&&\\ \hline 2&3&&&&& \\ \hline 4&6&9&&&& \\ \hline 8&12&18&27&&& \\ \hline 16&24&36&54&81&& \\ \hline 32&48&72&108&162&243& \\ \hline 64&96&144&216&324&486&729 \\ \hline 128&192&288&432&648&972&1458 \\ \hline 246&384&576&864&1296&1944& \\ \hline 512&768&1152&1728&&& \\ \hline 1024&1536&&&&& \\ \hline \end{array}$$ 按 $a$ 的值依次对集合作分划，如 $$\begin{split}&\{1\cdot 1\},\{1\cdot 2,1\cdot 3\},\{1\cdot 4,1\cdot 6\},\{1\cdot 9\},\cdots ,\{1\cdot 1296,1\cdot 1944\},\\ &\{5\cdot 5\},\{5\cdot 2,5\cdot 3\},\{5\cdot 4,5\cdot 6,\},\{5\cdot 9\},\cdots,\{5\cdot 246,5\cdot 384\},\\ &\cdots \\ &\{2017\cdot 1\},\end{split}$$ 则分划中每个集合至多取一个元素．接下来我们去掉所有 $b$ 取第 $2,4,6$ 列的数，则此时分划中每个集合恰好只取一个元素．列表辅助计数 $$\begin{array} {c|ccccccc}\hline n&1&2&3&4&5&6&7\\ \hline b&3&6&12&24&27&48&54\\ \hline \left[\dfrac{2018}{b}\right]&672&336&168&84&74&42&37\\ \hline n&8&9&10&11&12&13&14\\ \hline b&96&108&192&216&243&384&432\\ \hline \left[\dfrac{2018}{b}\right]&21&18&10&9&8&5&4\\ \hline n&15&16&17&18&19&20&21\\ \hline b&486&768&864&972&1536&1728&1944\\ \hline \left[\dfrac{2018}{b}\right]&4&2&2&2&1&1&1\\ \hline\end{array}$$ 因此当 $a$ 取不同值时需要去掉的数分别为 $$\begin{array} {c|c|c|c}\hline a&num(a)&num(b)&num(a)\cdot num(b)\\ \hline 1&1&21&21\\ \hline 5&1&13&13\\ \hline 7&1&12&12\\ \hline 11,13,17&3&9&27\\ \hline 19&1&8&8\\ \hline 23,25,\cdots,37&6&7&42\\ \hline 41&1&6&6\\ \hline 43,47,\cdots,73&11&5&55\\ \hline 77,79,83&3&4&12\\ \hline 85,89,\cdots,167&28&3&84\\ \hline 169,173,\cdots,337&57&2&114\\ \hline 341,343,\cdots,671&111&1&111\\ \hline &&{\rm SUM}&505\\ \hline \end{array}$$ 因此一共要去掉 $505$ 个数，所求 $k$ 的最大值为 $1513$．