2010 USAJMO Problems/Problem 2

Problem

Let $n > 1$ be an integer. Find, with proof, all sequences $x_1, x_2, \ldots, x_{n-1}$ of positive integers with the following three properties:

  1. (a). $x_1 < x_2 < \cdots <x_{n-1}$;
  2. (b). $x_i +x_{n-i} = 2n$ for all $i=1,2,\ldots,n-1$;
  3. (c). given any two indices $i$ and $j$ (not necessarily distinct) for which $x_i + x_j < 2n$, there is an index $k$ such that $x_i+x_j = x_k$.

Solution

The sequence is $2, 4, 6, \ldots, 2n-2$.

Proof

We will prove that any sequence $x_1, \ldots, x_{n-1}$, that satisfies the given conditions, is an arithmetic progression with $x_1$ as both the first term and the increment. Once this is proved, condition (b) implies that $x_1 + x_{n-1} = x_1 + (n-1)x_1 = nx_1 = 2n$. Therefore $x_1 = 2$, and the sequence is just the even numbers from $2$ to $2n-2$. The sequence of successive even numbers clearly satisfies all three conditions, and we are done.

First a degenerate case. If $n = 2$, there is only one element $x_1$, and condition (b) gives $x_1 + x_1 = 4$ or $x_1 = 2$. Conditions (a) and (c) are vacuously true.

Otherwise, for $n > 2$, we will prove by induction on $m$ that the difference $x_{n-m} - x_{n-1-m} = x_1$ for all $m \in [1, n-2]$, which makes all the differences $x_{n-1} - x_{n-2} = \ldots = x_2 - x_1 = x_1$, i.e. the sequence is an arithmetic progression with $x_1$ as the first term and increment as promised.

So first the $m=1$ case. With $n > 2$, $x_{n-2}$ exists and is less than $x_{n-1}$ by condition (a). Now since by condition (b) $x_1 + x_{n-1} = 2n$, we conclude that $x_1 + x_{n-2} < 2n$, and therefore by condition (c) $x_1 + x_{n-2} = x_k$ for some $k$. Now, since $x_1 > 0$, $x_k > x_{n-2}$ and can only be $x_{n-1}$. So $x_1 + x_{n-2} = x_{n-1}$.

Suppose we have shown that for all $i \le m$, $x_1 + x_{n-1-i} = x_{n-i}$. If $m = n-2$ we are done, otherwise $m < n-2$, and by condition (c) $x_1 + x_{n-2-m} = x_k$ for some $k$. This $x_k$ is larger than $x_{n-2-m}$, but smaller than $x_1 + x_{n-1-m} = x_{n-m}$ by the inductive hypothesis. It then follows that $x_1 + x_{n-2-m} = x_{n-1-m}$, the only element of the sequence between $x_{n-2-m}$ and $x_{n-m}$. This establishes the result for $i=m+1$.

So, by induction $x_1 + x_{n-1-m} = x_{n-m}$ for all $m \in [1, n-2]$, which completes the proof.

See Also

2010 USAJMO (ProblemsResources)
Preceded by
Problem 1
Followed by
Problem 3
1 2 3 4 5 6
All USAJMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png