每日一题[2748]截断

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

答案    $1514$.

解析    任何一个正整数必然可以写成 $2^p\cdot 3^q\cdot r$ 的形式,其中 $2\nmid r$,$3\nmid r$ 且 $p,q\in \mathbb N$,$r\in\mathbb N^{\ast}$.按每个正整数对应的 $(p,q)$ 做分划,有\[\begin{array}{c|c|c|c|c|c|c|c}\hline p/q&0&1&2&3&4&5&6\\ \hline 0&1,5,7,\cdots&3,15,21,\cdots&9,45,63,\cdots&27,135,189,\cdots&81,405,567,\cdots&243,1215,1701&729\\ \hline 1&2,10,14,\cdots&6,30,42,\cdots&18,90,126,\cdots&54,270,378,\cdots&\cdots&\cdots&1458\\ \hline 2&4,20,28,\cdots&12,60,84,\cdots&36,180,252,\cdots&\cdots&\cdots&\cdots& \\ \hline 3&8,40,56,\cdots&24,120,168,\cdots&\cdots&\cdots&\cdots&\cdots&\\ \hline 4&16,80,112,\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\\ \hline 5&32,160,224,\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\\ \hline 6&64,320,448,\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\\ \hline 7&128,640,896,\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\\ \hline 8&256,1280,1792&\cdots&\cdots&\cdots&\cdots&\cdots&\\ \hline 9&512&\cdots&\cdots&\cdots&\cdots&\cdots&\\ \hline 10&1024&\cdots&\cdots&\cdots&\cdots&\cdots&\\ \hline \end{array}\] 设 $x>y$ 且 $x,y\in\{1,2,\cdots,2018\}$,则 $\dfrac xy=\dfrac 32$ 等价于 $x,y$ 位于 $p+q$ 的值相等的相邻斜格.下面证明 $k$ 的最大值为 $1514$.记 $N(p,q)$ 为 $(p,q)$ 对应的格子中的元素个数.

构造    去掉 $q=1,3,5$ 列中的所有格子里的元素,剩下的元素符合题意.考虑到 $q$ 列格子元素个数之和\[T_q=\sum_{p=0,1,\cdots,10}N(p,q)=\left\lfloor\dfrac{2018}{3^q}\right\rfloor-\left\lfloor\dfrac{2018}{3^{q+1}}\right\rfloor,\]而\[\begin{array}{c|ccccccc}\hline q&0&1&2&3&4&5&6\\ \hline \left\lfloor\dfrac{2018}{3^q}\right\rfloor&2018&672&224&74&24&8&2\\ \hline \left\lfloor\dfrac{2018}{3^q}\right\rfloor-\left\lfloor\dfrac{2018}{3^{q+1}}\right\rfloor&1346&448&150&50&16&6&2\\ \hline\end{array}\] 此时元素个数之和为\[\sum_{q=0,2,4,6}T_q=2+16+150+1346=1514.\]

论证    考虑 $p+q=m$($m=0,1,2,\cdots,10$)的斜格,记为斜格组\[U_m:(0,m),(1,m-1),\cdots,(m,0),\]每个斜格组中的数可以写成 $N(0,m)$ 个数链,如 $m=3$ 的情形,有\[\begin{split} &8,12,18,27;\\ &40,60,90,135;\\ &56,84,126,189;\\ &\cdots, \end{split}\]长度为 $l$ 的数链中至多取 $\left\lceil \dfrac l2\right\rceil$ 个数,因此至少要去掉的元素个数为\[\sum_{q=1,3,5}T_q=504.\] 综合所述,$k$ 的最大值为 $1514$.

备注    长度为奇数的数链取数方法是唯一的,长度为 $2n$ 的数链取数方法有 $n+1$ 种,因此可以在此基础上思考最大集合的个数.长度为 $l$ 的数链个数 $n(l)$ 分别为\[\begin{array}{c|ccccccc}\hline l&1&2&3&4&5&6&7\\ \hline n(l)&898&298&100&34&10&4&2\\ \hline\end{array}\]因此所求最大集合的个数为 $2^{298}\cdot 3^{34}\cdot 4^4$.

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

发表回复