Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2010 USAJMO Problems/Problem 2"
m (→‎Proof: Added clarification)
Line 42: Line 42:
 
x_{n-2} = x_{n-1}</math>.
 
x_{n-2} = x_{n-1}</math>.
  
 +
Now for the induction step on all values of <math>m</math>.
 
Suppose we have shown that for all <math>i \le m</math>, <math>x_1 + x_{n-1-i} =
 
Suppose we have shown that for all <math>i \le m</math>, <math>x_1 + x_{n-1-i} =
 
x_{n-i}</math>.  If <math>m = n-2</math> we are done, otherwise <math>m < n-2</math>, and by
 
x_{n-i}</math>.  If <math>m = n-2</math> we are done, otherwise <math>m < n-2</math>, and by

Revision as of 16:31, 5 April 2018

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}$.

Now for the induction step on all values of $m$. 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 (Problems • Resources)
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_USAJMO_Problems/Problem_2&oldid=93820"