问题及解答

从 $1,2,3,\ldots,100$ 中, 最多可取出多少个数, 使得取出的数中任意两个数之和不是此两数之差的倍数.
 

记 $X=\{1,2,3,\ldots,100\}$. 要从 $X$ 中取出一个子集 $A$, 使得任取 $x,y\in A$, $x+y$ 不能被 $|x-y|$ 整除. 我们要使得 $\#A$ (也就是 $A$ 所含元素的个数)尽可能的大.

显然 $A$ 中不能包含相邻的数, 也不能包含相隔为 2 的两个数. (后者的原因是 $a+(a+2)=2a+2$ 一定被 2 整除.)

于是我们考虑 $A$ 由 $X$ 中相隔为 3 的数组成. 为使得 $\#A$ 尽可能大. 显然令

\[
A=\{1,4,7,10,13,16,\ldots,97,100\}
\]

$\# A=34$.

我们说这个子集 $A$ 是符合题目要求的.

事实上, 任取 $x=3k+1, y=3\ell+1\in A$ (不妨设 $y > x$), 于是

\[
x+y=3(k+\ell)+2,\quad y-x=3(\ell-k).
\]

显然 $(y-x)\not| (x+y)$.

因此, 答案是 34.