2009 USAMO Problems/Problem 2

Problem

Let $n$ be a positive integer. Determine the size of the largest subset of $\{ - n, - n + 1, \ldots , n - 1, n\}$ which does not contain three elements $a, b, c$ (not necessarily distinct) satisfying $a + b + c = 0$ .

note, pardon the notation.

Let $Z_n$ be the set of subsets satisfying the $a+b+c \neq 0$ condition for $n$ , and let $s_n$ be the largest size of a set in $Z_n$ . Let $n = 2k$ if $n$ is even, and $n = 2k-1$ if $n$ is odd. We note that $s_n \ge 2k$ due to the following constuction: $\{-2k+1, -2k + 3, \ldots, 2k-3, 2k-1\}$ or all of the odd numbers in the set. Then the sum of any three will be odd and thus nonzero.

Lemma 1: $s_{n+1} \le s_{n} + 2$ . If $M_{n+1} \in Z_{n+1}, |M_{n+1}| = s_{n+1}$ , then we note that $M_{n+1} \setminus \{-2n+1, 2n-1\} \in Z_n$ , so $|M_{n+1}| - 2 \le s_n$ . $\square$

Lemma 2: $s_{2k} = s_{2k-1}$ . Suppose, for sake of contradiction, that $M_{2k} \in Z_{n+1}$ and $M_{2k} > s_{2k-1}$ . Remove $2k,-2k$ from $M_{2k}$ , and partition the rest of the elements into two sets $P_{2k-1}, Q_{2k-1}$ , where $P$ and $Q$ contain all of the positive and negative elements of $M_{2k}$ , respectively. (obviously $0 \not \in M_{2k}$ , because $0+0+0 = 0$ ). WLOG, suppose $|P_{2k-1}| \ge |Q_{2k-1}|$ . Then $|P_{2k-1}| + |Q_{2k-1}| \ge s_{2k-1} - 1 \ge 2k - 1$ . We now show the following two sub-results:

Sub-lemma (A): if $|P_{2k-1}| \ge k$ , $-2k \not \in M_{2k}$ [and similar for $Q$ ]; and

Sub-lemma (B): we cannot have both $|P_{2k-1}| + |Q_{2k-1}| \ge 2k$ and $|Q_{2k-1}| < k$ simultaneously hold.

This is sufficient, because the only two elements that may be in $M_{2k}$ that are not in $P_{2k-1}, Q_{2k-1}$ are $2k$ and $-2k$ ; for $M_{2k} > s_{2k-1}$ , we must either have $|P_{2k-1}| + |Q_{2k-1}| = s_{2k-1} - 1 \ge 2k-1$ and both $2k,-2k \in M_{2k}$ [but by pigeonhole $|P_{2k-1}| \ge k$ , see sub-lemma (A)], or $|P_{2k-1}| + |Q_{2k-1}| = s_{2k-1} \ge 2k$ , and $2k \in M_{2k}$ , in which case by (A) we must have $|Q_{2k-1}| < k$ , violating (B).

(B): We prove this statement with another induction. We see that the statement easily holds true for $k=1$ or $2$ , so suppose it is true for $k-1$ , but [for sake of contradiction] false for $k$ . Let $P_{2k-3} = P_{2k-1} \setminus \{2k-2, 2k-1\}$ , and similarly for $Q_{2k-3}$ . Again WLOG $|P_{2k-3}| \ge |Q_{2k-3}|$ . Then we have $|P_{2k-1}| + |Q_{2k-1}| \le |P_{2k-3}| + |Q_{2k-3}| + 4$ .