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"

(Created page with '==Problem== Let <math>n > 1</math> be an integer. Find, with proof, all sequences <math>x_1, x_2, \ldots, x_{n-1}</math> of positive integers with the following three properties:…')
 
(→‎Proof)
Line 52: Line 52:
 
So, by induction <math>x_1 + x_{n-1-m} = x_{n-m}</math> for all <math>m \in [1, n-2]</math>,
 
So, by induction <math>x_1 + x_{n-1-m} = x_{n-m}</math> for all <math>m \in [1, n-2]</math>,
 
which completes the proof.
 
which completes the proof.
 +
 +
== See Also ==
 +
{{USAJMO newbox|year=2010|num-b=1|num-a=3}}
 +
 +
[[Category:Olympiad Number Theory Problems]]

Revision as of 20:13, 28 March 2013

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 (Problems • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_USAJMO_Problems/Problem_2&oldid=51950"