问题及解答

从 $1,2,3,\ldots,2017$ 这 2017 个正整数中, 至少任意取出多少个数, 才能保证取出的这些数中, 有一个数是另一个数的两倍?

记 $X=\{1,2,3,\ldots,2017\}$. 现在要找 $X$ 的子集 $A$, 使得 $A$ 满足条件:

\[\forall\ x\in A,\quad 2x\not\in A.\qquad(*)\]

我们要找的是 $\# A$ 达到最大的子集 $A$.

Step 1.  保留 $X$ 中的奇数, 即 $\{x\in X\mid x=2k+1\}\subset A$. 对于剩下的偶数

\[
\begin{matrix}
2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & \cdots\\
1 &   & 3 &  & 5 &  & 7 &  & 9 &  & 11 &  & \cdots
\end{matrix}
\]

由于 $1\in A$, 因此删除上面 $2,6,10,14,18,22,\ldots$. 余下的是形如 $4k$ 的数.

也就是说, 第一步是 $X=\{k\}\mapsto\{2^2 k\}\cap X$, 其中删除了形如 $2(2k+1)$ 的数. 这些数是

\[
\{2+4d\mid d=0,1,2,\ldots,503\},
\]

共 504 个.

Step 2.  $\{2^2 k\}\cap X\mapsto\{2^4 k\}\cap X$, 其中删除了形如 $2^3 (2k+1)$ 的数. 这些数是

\[
\{8+16d\mid d=0,1,2,\ldots,125\},
\]

共 126 个.

Step 3.  $\{2^4 k\}\cap X\mapsto\{2^6 k\}\cap X$, 其中删除了形如 $2^5 (2k+1)$ 的数. 这些数是

\[
\{32+64d\mid d=0,1,2,\ldots,31\},
\]

共 32 个.

Step 4.  $\{2^6 k\}\cap X\mapsto\{2^8 k\}\cap X$, 其中删除了形如 $2^7 (2k+1)$ 的数. 这些数是

\[
\{128+256d\mid d=0,1,2,\ldots,7\},
\]

共 8 个.

Step 5.  $\{2^8 k\}\cap X\mapsto\{2^{10} k\}\cap X$, 其中删除了形如 $2^9 (2k+1)$ 的数. 这些数是

\[
\{512+1024d\mid d=0,1\},
\]

共 2 个.

Step 6. 注意 $\{1024k\mid k=1,2,\ldots\}\cap X$ 中形如 $2^{11}(2k+1)$ 的数没有.

故需要删除的数总共有 $504+126+32+8+2=672$, 因此, 满足上面性质 $(*)$ 的集合 $A$ 所含元素个数是 $2017-672=1345$.

于是 $X$ 中至少要取 1346 个元素(组成集合 $B$), 才能保证存在 $m$, 使得 $\{m,2m\}\subset B$.

如果理解了上面的做法, 最简洁的做法是:

\[
1009+(504-252)+(126-63)+(31-15)+(7-3)+1=1345.
\]

其中 $1009$ 是 $X=\{1,2,3,\ldots,2017\}$ 中奇数的个数. 其他的一看就明白了.

Provided by David Chen.