Let $X=\{1,2,\ldots,2001\}$. Find the least positive integer $m$ such that for each subset $W\subset X$ with $m$ elements, there exist $u,v\in W$ (not necessarily distinct) such that $u+v$ is of the form $2^{k}$, where $k$ is a positive integer.
Problem
Source: 2001 China National Olmpiad
Tags: number theory proposed, number theory
19.01.2013 15:29
Answer: 1 + 2 + 2^2 +... + 2^9 = 1023 Lemma: For any given number k, then among 2^(k - 1) + 1 numbers in the interval ( 2^k, 2^(k+1) ), there are always two numbers whose sum equals to 2^(k+1)
25.01.2013 11:53
It's wrong I've proofed that it's less than 683 take sets A,B,C A={a1,a2,a3,...,ak} B={2^11-a1,2^11-a2,...} C={2^10-a1,...} then we have that if two of this numbers are equal the condition doesn't hold And for n>=683 it's obvious that it does not hold!!!!
25.01.2013 15:26
${A_i} = \left\{ {1024 - i,1024 + i} \right\},1 \leqslant i \leqslant 977$;${B_j} = \left\{ {32 - j,32 + j} \right\},1 \leqslant j \leqslant 14$;${C_k} = \left\{ {8 - k,8 + k} \right\},1 \leqslant k \leqslant 6$; $D = \left\{ {15,17} \right\}$; $E = \left\{ {1,8,16,32,1024} \right\}$. Then $X = \left( {\bigcup\limits_{i = 1}^{977} {{A_i}} } \right) \cup \left( {\bigcup\limits_{j = 1}^{14} {{B_j}} } \right) \cup \left( {\bigcup\limits_{k = 1}^6 {{C_k}} } \right) \cup D \cup E$, If $\left| W \right| = 999$, and $W \cap E = \emptyset $, then $W \subseteq \left( {\bigcup\limits_{i = 1}^{977} {{A_i}} } \right) \cup \left( {\bigcup\limits_{j = 1}^{14} {{B_j}} } \right) \cup \left( {\bigcup\limits_{k = 1}^6 {{C_k}} } \right) \cup D$, so there exist $u,v \in W$ belong a same subset, so $u + v$ is of the form ${2^\alpha }$. On the other hand, if $W = \left\{ {1025,1026,...,2001} \right\} \cup \left\{ {33,34,...,46} \right\} \cup \left\{ {9,10,...,15} \right\}$, $\left| W \right| = 998$, and for any $u,v \in W$, $u + v$ is not power of $2$. Above all, $m=999$ is the solution.