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:

(a). $x_1 < x_2 < \cdots <x_{n-1}$ ;
(b). $x_i +x_{n-i} = 2n$ for all $i=1,2,\ldots,n-1$ ;
(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.

Page

Toolbox

Search

2010 USAJMO Problems/Problem 2

Problem

Solution

Proof