设 $X=\{1,2, \cdots, 2001\}$．求最小正整数 $m$，适合要求：对 $X$ 的任何一个 $m$ 元子集 $W$，都存在 $u, v \in W$（$u$ 和 $v$ 可以相同），使得 $u+v$ 是 $2$ 的方幂
【难度】
【出处】
2001第16届CMO试题
【标注】
【答案】
略
【解析】
将 $X$ 分成以下 $5$ 个子集进行考察：
$2001=1024+977 \geqslant x \geqslant 1024-977=47$
$46=32+14 \geqslant x \geqslant 32-14=18$
$17=16+1 \geqslant x \geqslant 16-1=15$
$14=8+6 \geqslant x \geqslant 8-6=2$
$x=1$
为了构造一个使题中要求不被满足且又含元素最多的例子，这个子集不能含 $2$ 的任一方幂且每对数 $\left\{2^{r}+a, 2^{r}-a\right\}$ 中只能有 $1$ 个含在集中．
令 $Y=\{2001,2000, \cdots, 1025\} \bigcup\{46,45, \cdots, 33\} \bigcup\{17\} \bigcup\{14,13, \cdots, 9\} \bigcup\{1\}$，则有 $\{Y\}=998$，且对任何 $u, v \in Y, u+v$ 都不是 $ 2$ 的方幂．事实上，当 $u, v \in Y$ 时，不妨设 $u \geqslant v$ 且有 $2^{r}<u \leqslant 2^{r}+a<2^{r+1}$，其中当 $r$ 分别取值 $10,5,4,3$ 时，相应的 $a$ 值依次为 $977,14,1,6$．
（i）若 $2^{r}<v \leqslant u$，则 $2^{r+1}<u+v<2^{r+2}$，$u+v$ 不能是 $2$ 的方幂．
（ii）若 $1 \leqslant v<2^{r}$，则当 $2^{r}<u \leqslant 2^{r}+a, 1 \leqslant a<2^{r}$ 时，$1\leqslant v<2^{r}-a$．于是 $2^{r}<u+v<2^{r+1}$ 这表明 $u+v$ 也不能是 $2$ 的方幂，所以子集 $Y$ 中 任何两数之和都不是 $2$ 的方幂．
故知所求的最小正整数 $m\geqslant 999$．
将 $X$ 划分成下列 $999$ 个互不相交的子集．
$A_{i}=\{1024-i, 1024+i\}, i=1,2, \cdots, 977$
$B_{i}=\{32-j, 32+j\}, j=1,2, \cdots, 14$
$C=\{15,17\}$
$D_{k}=\{8-k, 8+k\}, k=1,2, \cdots, 6$
$E=\{1,8,16,32,1024\}$
对于 $S$ 的任何一个 $999$ 元子集 $W$．若 $W \cap E \neq \varnothing$，则从其中任取一个元素的 $2$ 倍都是 $2$ 的方幂；若 $W \cap E \neq \varnothing$，则 $W$ 中的 $999$ 个元素分属于前面的 $998$ 个 $2$ 元子集．由抽屉原理知 $W$ 中必有不同的 $u$ 和 $v$ 屑于其中同一子集．显然，$ u+v$ 为 $2$ 的方幂．
综上可知，所求的最小正整数 $m = 999$．
$2001=1024+977 \geqslant x \geqslant 1024-977=47$
$46=32+14 \geqslant x \geqslant 32-14=18$
$17=16+1 \geqslant x \geqslant 16-1=15$
$14=8+6 \geqslant x \geqslant 8-6=2$
$x=1$
为了构造一个使题中要求不被满足且又含元素最多的例子，这个子集不能含 $2$ 的任一方幂且每对数 $\left\{2^{r}+a, 2^{r}-a\right\}$ 中只能有 $1$ 个含在集中．
令 $Y=\{2001,2000, \cdots, 1025\} \bigcup\{46,45, \cdots, 33\} \bigcup\{17\} \bigcup\{14,13, \cdots, 9\} \bigcup\{1\}$，则有 $\{Y\}=998$，且对任何 $u, v \in Y, u+v$ 都不是 $ 2$ 的方幂．事实上，当 $u, v \in Y$ 时，不妨设 $u \geqslant v$ 且有 $2^{r}<u \leqslant 2^{r}+a<2^{r+1}$，其中当 $r$ 分别取值 $10,5,4,3$ 时，相应的 $a$ 值依次为 $977,14,1,6$．
（i）若 $2^{r}<v \leqslant u$，则 $2^{r+1}<u+v<2^{r+2}$，$u+v$ 不能是 $2$ 的方幂．
（ii）若 $1 \leqslant v<2^{r}$，则当 $2^{r}<u \leqslant 2^{r}+a, 1 \leqslant a<2^{r}$ 时，$1\leqslant v<2^{r}-a$．于是 $2^{r}<u+v<2^{r+1}$ 这表明 $u+v$ 也不能是 $2$ 的方幂，所以子集 $Y$ 中 任何两数之和都不是 $2$ 的方幂．
故知所求的最小正整数 $m\geqslant 999$．
将 $X$ 划分成下列 $999$ 个互不相交的子集．
$A_{i}=\{1024-i, 1024+i\}, i=1,2, \cdots, 977$
$B_{i}=\{32-j, 32+j\}, j=1,2, \cdots, 14$
$C=\{15,17\}$
$D_{k}=\{8-k, 8+k\}, k=1,2, \cdots, 6$
$E=\{1,8,16,32,1024\}$
对于 $S$ 的任何一个 $999$ 元子集 $W$．若 $W \cap E \neq \varnothing$，则从其中任取一个元素的 $2$ 倍都是 $2$ 的方幂；若 $W \cap E \neq \varnothing$，则 $W$ 中的 $999$ 个元素分属于前面的 $998$ 个 $2$ 元子集．由抽屉原理知 $W$ 中必有不同的 $u$ 和 $v$ 屑于其中同一子集．显然，$ u+v$ 为 $2$ 的方幂．
综上可知，所求的最小正整数 $m = 999$．
答案
解析
备注
