Problem 1855

First Solution. (By Reid Barton) For a positive integer $n$, let $Z_n$ denote the set of residues modulo $n$. Let $\phi(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' \pmod{3^n}, m' \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) \pmod{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 \pmod{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| = \phi(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' \in A_i$ (where $m \equiv m' \pmod{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 \neq 0$, as $z$ ranges over $Z_{3^{n+1}}$, one third of the residues $zm$ are in $C$; likewise, since $3m \neq 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 \bmod 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 \pmod 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.
$\blacksquare$

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.

Second Solution. Let the elements of $A$ be $a_1, \dots, a_{2001}$. Let $p$ be a prime number such that $p \equiv 2 \pmod 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 $ka_i$ is mediocre. Thus, there are
$$\frac{2001(p+1)}{3} = 667(p+1)$$
pairs of $(k, i)$ such that $ka_i$ is mediocre. By the Pigeonhole Principle, there exists some $k$ for which the set
$$B = \{a_i \mid ka_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.