China Team Selection Test

For a positive integer $n$, and a non-empty subset $A$ of $\{1, 2, \ldots, 2n\}$, we call $A$ good if the set $\{u \pm v \mid u, v \in A\}$ does not contain the set $\{1, 2, \ldots, n\}$. We aim to find the smallest real number $c$ such that for any positive integer $n$, and any good subset $A$ of $\{1, 2, \ldots, 2n\}$, $|A| \leq cn$.

We will prove that the smallest constant is $c = \frac{6}{5}$.

First, let us show that $c \geq \frac{6}{5}$. Consider $n = 10q + 1$ for $q \in \mathbb{N}_0$ and set $k = \frac{4n + 1}{5}$. Observe that $k$ is an odd positive integer with $1 \leq k \leq n$. Now, consider the set $A = A_1 \cup A_2 \cup A_3$ where
$$A_1 = \left\{1, 2, \ldots, \frac{k - 1}{2}\right\}, \quad A_2 = \left\{2k + 1, 2k + 2, \ldots, 2k + \frac{k - 1}{2}\right\}, \quad A_3 = \left\{ k + \frac{k + 1}{2}, k + \frac{k + 3}{2}, \ldots, 2k\right\}.$$
It is clear that $A$ is a subset of $\{1, 2, \ldots, 2n\}$ with
$$|A| = \frac{k - 1}{2} + \left(k - \frac{k - 1}{2}\right) + \frac{k - 1}{2} = \frac{6}{5}n - \frac{1}{5}.$$
Hence, if we take the limit as $q \to \infty$, it follows that $|A| > \epsilon n$ for any $\epsilon < \frac{6}{5}$. Therefore, to show that $c \geq \frac{6}{5}$, it suffices to prove that $A$ is good. In particular, we will show that the set $B = \{u \pm v \mid u, v \in A\}$ does not contain the integer $k$.

First, it is clear that if $u, v \in A$ satisfy $u + v = k$, then $u, v \in A_1$ (since all elements of $A_2$ and $A_3$ are greater than $k$). However, this is impossible, since the greatest possible sum of two elements of $A_1$ is $\frac{k - 1}{2} + \frac{k - 3}{2} < k$. Meanwhile, if $u, v \in A$ satisfy $u - v = k$, we must have $u \equiv v \pmod{k}$. By breaking up $A$ into subsets modulo $k$, we find that
$$A = \{1, 2k + 1\} \cup \{2, 2k + 2\} \cup \cdots \cup \left\{\frac{k - 1}{2}, 2k + \frac{k - 1}{2}\right\} \cup \left\{k + \frac{k + 1}{2}\right\} \cup \left\{k + \frac{k + 3}{2}\right\} \cup \cdots \cup \{2k\}.$$
It is then easy to see that no $u, v \in A$ satisfy $u - v = k$. Hence, $c \geq \frac{6}{5}$, as desired. $\blacksquare$

Now, we will show that $|A| \leq \frac{6}{5}n$ for any good set $A \subseteq \{1, 2, \ldots, 2n\}$. Suppose, by way of contradiction, that there exists a good set $A \subseteq \{1, 2, \ldots, 2n\}$ with $|A| > \frac{6}{5}n$. Then there must exist some integer $k \in \{1, 2, \ldots, n\}$ such that $k \not\in B$, where $B = \{u \pm v \mid u, v \in A\}$.

By the Division Algorithm, let us write $2n = mk + p$ where $m \in \mathbb{N}$ and $0 \leq p < k$. In particular, notice that
$$2n = mk + p < (m + 1)k \leq (m + 1)n \implies 2 < m + 1 \implies 2 \leq m.$$
Now, consider the sets $S_i = \{b \in B \mid b \equiv i \pmod{k}\}$ ($i = 1, 2, \ldots, k$). We will examine these sets in pairs: $(S_1, S_{k - 1}), (S_2, S_{k - 2}), \ldots$. First, observe that the only sets that are not part of a pair are $S_k$ and $S_{k / 2}$ (if $k$ is even).

We begin by proving that at most $\frac{m + 1}{2m + 1}$ of the elements in $S_k \cup S_{k / 2}$ are in $B$ (if $k$ is odd, simply ignore the set $S_{k / 2}$ in the following analysis; the same conclusion still holds). Observe that $S_k$ has precisely $m$ elements, and $S_{k / 2}$ has either $m$ or $m + 1$ elements. Within each of these sets, no two consecutive elements can both be in $B$, since then the difference of these two consecutive elements would equal $k$, a contradiction. Hence, at most $\left\lceil \frac{m}{2} \right\rceil$ of the elements in $S_k$ are in $B$, and at most $\left\lceil \frac{m + 1}{2} \right\rceil$ of the elements in $S_{k / 2}$ are in $B$. It is then easy to see that at most $\frac{m + 1}{2m + 1}$ of the elements in $S_k \cup S_{k / 2}$ are in $B$.

Now, we prove a similar bound for the pairs of sets described earlier: Consider any pair $(S_i, S_{k - i})$. Notice that at most $\frac{1}{2}$ of the elements of one of these sets can be in $B$. This is because if more than $\frac{1}{2}$ of the elements of each of these sets are in $B$, then because no two consecutive elements in either of these sets can be in $B$, it would follow that $i \in S_i$ and $k - i \in S_{k - i}$ must be in $B$. However, this is impossible, since then the sum of these two elements would equal $k$, a contradiction. Therefore, at most $\frac{1}{2}$ of the elements in one of these two sets must be in $B$. Keeping in mind that $|S_i| = m, m + 1$, it’s not hard to see that at most $\frac{m + 1}{2m + 1}$ of the elements in $S_i \cup S_{k - i}$ are in $B$.

Therefore, since $B \subseteq S_1 \cup S_2 \cup \cdots \cup S_k$, it follows that
$$|B| \leq \frac{m + 1}{2m + 1} |S_1 \cup S_2 \cup \cdots \cup S_k| = \frac{m + 1}{2m + 1}(2n).$$
Because $\frac{m + 1}{2m + 1} = \frac{1}{2} + \frac{1}{4m + 2}$ is a decreasing function of $n$ over $\mathbb{N}$, it follows that $\frac{m + 1}{2m + 1}$ takes on its maximal value for $m = 2$. Hence,
$$|B| \leq \frac{2 + 1}{4 + 1}(2n) = \frac{6}{5}n.$$
This is a clear contradiction, since we assumed that $|B| > \frac{6}{5}n$. Thus, the proof is complete. $\square$

The answer is $\boxed{\frac{6}{5}}$.