USA IMO

First Solution. (By Reid Barton) For a positive integer $n$, let $Z_n$ denote the set of residues modulo $n$. Let $\varphi (n)$ be the Euler function which is defined to be the number of integers between $1$ and $n$ relatively prime to $n$. Call a set $A$ of residues modulo $3^n$ sum-free if for any $a,b\in A$, $a+b$ is not (congruent to) an element of $A$.

Lemma. For any $n\ge 1$, there exist $3^n-1$ sum-free sets of $3^{n-1}$ residues modulo $3^n$ such that every nonzero residue modulo $3^n$ appears in exactly $3^{n-1}$ of the subsets.

Proof. We construct the desired subsets inductively. For $n=1$ we take the sets $\{1\}$ and $\{2\}$.

Let $n\ge 1$, and suppose that the statement holds for $n$, that is, we have $3^n-1$ sum-free subsets $A_1,A_2,\dots ,A_{3^{n-1}}$ of $Z_{3^n}$ such that every nonzero element of $Z_{3^n}$ belongs to exactly $3^{n-1}$ of the $A_i$. Construct sets $B_1,B_2,\dots ,B_{3^{n-1}}$ by $$B_i=\{x\in Z_{3^{n+1}}\mid x\equiv m^{\prime }(\mathrm{mod}{3}^n),m^{\prime }\in A_i\}.$$ Then each $B_i$ contains $3|A_i|=3^n$ residues, and the $B_i$ are sum-free, because if $a,b\in B_i$, $(a+b)(\mathrm{mod}{3}^n)$ is not in $A_i$ so $a+b$ is not in $B_i$. Moreover, each element $x$ of $Z_{3^{n+1}}$ which is not $0$ modulo $3^n$ (i.e., all elements except $0,3^n,2\cdot 3^n$) is in exactly $3^{n-1}$ of the $B_i$, namely those corresponding to the $A_i$ containing $x(\mathrm{mod}{3}^n)$.

Now define sets $$C=\{3^n,3^n+1,\dots ,2\cdot 3^n-1\}$$ and $$U=\{x\in Z_{3^{n+1}}\mid \gcd (x,3)=1\}.$$ Then $C\subset Z_{3^{n+1}}$, $|C|=3^n$. Note that $C$ is sum-free, because if $a,b\in C$ with $3^n\le a,b<2\cdot 3^n$ then $2\cdot 3^n\le a+b<4\cdot 3^n$ so $a+b$ is not congruent modulo $3^{n+1}$ to an element of $C$. For each $y\in U$, let $C_y=yC=\{yx\mid x\in C\}$. Then $C_y$ is also sum-free for every $y\in U$, because if we had $ya$ and $yb$ in $C_y$ with $ya+yb\in C_y$, then $a$ and $b$ would be elements of $C$ summing to an element of $C$. Also, every $C_y$ contains $|C|=3^n$ residues because multiplication by $y$ is invertible. Since $|U|=\varphi (3^{n+1})=2\times 3^n$, there are $2\cdot 3^n$ of sets $C_y$.

Consider the sets $B_1,B_2,\dots ,B_{3^{n-1}},C_1,C_2,C_4,C_5,C_7,\dots ,C_{3^{n+1}-2},C_{3^{n+1}-1}$. There are $3^n-1+2\cdot 3^n=3^{n+1}-1$ of these sets, so it suffices to check that every nonzero residue modulo $3^{n+1}$ appears in exactly $3^n$ of them.

Let $m$ be a nonzero residue modulo $3^{n+1}$, and write $m=3^{k}s$, $0\le k\le n$, $\gcd (s,3)=1$. We consider two cases.

(i) $k<n$. Then $m$ is a nonzero residue modulo $3^n$, so $m$ is contained in exactly $3^{n-1}$ of the sets $B_i$, namely those which correspond to $A_i$ with $m^{\prime }\in A_i$ (where $m\equiv m^{\prime }(\mathrm{mod}{3}^n)$). The number of sets $C_i$ containing $m$ is the number of solutions to $y^{-1}m\in C$ with $y\in U$, or the number of $z\in U$ such that $zm\in C$. Since $m\ne 0$, as $z$ ranges over $Z_{3^{n+1}}$, one third of the residues $zm$ are in $C$; likewise, since $3m\ne 0$, one third of the residues $3zm$ are in $C$. Since $U=Z_{3^{n+1}}\setminus 3Z_{3^{n+1}}$, $zm\in C$ for one third of the values $z\in U$. So $m$ is in one third of the sets $C_y$, giving $\frac{1}{3}|U|=2\cdot 3^{n-1}$ more sets containing $m$. The total number of sets containing $m$ is then $3^{n-1}+2\cdot 3^{n-1}=3^n$.

(ii) $k=n$. Then $m=3^n$ or $2\cdot 3^n$ ($s=1$ or $2$ respectively). Then $m\mathrm{mod}{3}^n=0$, so $m$ does not appear in any of the sets $A_i$. However, $m$ appears in every set $C_y$ with $y\equiv s(\mathrm{mod}3)$, so $m$ appears in $3^n$ of the $C_y$. Thus the total number of sets containing $m$ is again $3^n$.

Thus the sets $\{B_i\}$, $\{C_y\}$ have the desired properties and the Lemma holds by induction. $■$

Now let $3^n$ be a power of $3$ larger than the sum of any two elements of $A$. By the Lemma, there exist $3^n-1$ sets $S_1,\dots ,S_{3^{n-1}}$ of $3^{n-1}$ residues modulo $3^n$ such that every nonzero residue modulo $3^n$ appears in exactly $3^{n-1}$ of the $S_i$. Let $n_i$ be the number of elements of $A$ contained in $S_i$. Since every element of $A$ appears $3^{n-1}$ times, $$\sum _{i=1}^{3^n-1}{n}_i=3^{n-1}|A|$$ so some $n_i$ is at least $$\frac{3^{n-1}|A|}{3^n-1}>\frac{1}{3}|A|=\frac{2001}{3}=667.$$ Let $B$ be the set of elements of $A$ contained in $S_i$. Then $|B|\ge 668$, and if $u,v\in B$, then $u+v\notin B$, because $S_i$ is sum-free. Thus the set $B$ has the desired properties.

---

Alternative solution.

Second Solution. Let the elements of $A$ be $a_1,\dots ,a_{2001}$. Let $p$ be a prime number such that $p\equiv 2(\mathrm{mod}3)$ and $p$ is larger than all the $a_i$. Such a prime $p$ exists by Dirichlet's Theorem, although the result can also be easily proven directly. There is at least one prime congruent to $2$ modulo $3$ (namely, $2$). Suppose there were only finitely many primes congruent to $2$ modulo $3$, and let their product be $P$. Then $3P-1$, which is larger than $P$ and congruent to $2$ modulo $3$, must have another prime divisor congruent to $2$ modulo $3$, contradiction. Thus, the original assumption was wrong, and there are infinitely many odd primes that are congruent to $2$ modulo $3$. Specifically, one such prime is larger than all $a_i$.

All elements of $S$ are distinct and nonzero modulo $p$. Call a number $n$ mediocre if the least positive residue of $n$ modulo $p$ lies in $[(p+1)/3,(2p-1)/3]$. For any $1\le i\le 2001$, there are exactly $(p+1)/3$ integer values of $k\in [1,p-1]$ such that $k{a}_i$ is mediocre. Thus, there are $$\frac{2001(p+1)}{3}=667(p+1)$$ pairs of $(k,i)$ such that $k{a}_i$ is mediocre. By the Pigeonhole Principle, there exists some $k$ for which the set $$B=\{a_i\mid k{a}_i\text{ is mediocre}\}$$ has at least $668$ elements.

We now claim that this $B$ satisfies the desired properties. It suffices to show that $k$ times the sum of any two elements of $B$ is not mediocre and hence cannot equal $k$ times any element of $B$. To that end, note that $k$ times the sum of any two elements of $B$ cannot be mediocre because it is congruent modulo $p$ to some number in $[2(p+1)/3,2(2p-1)/3]$ or, equivalently, to some number in $[0,(p-2)/3]\cup [(2p+2)/3,p-1]$, which is a set containing no mediocre numbers. Thus, the set $B$ satisfies the desired properties.