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"

(→‎Solution 3)
(Added a third solution that I think is nice.)
 
(6 intermediate revisions by 2 users not shown)
Line 14: Line 14:
 
The sequence is <math>2, 4, 6, \ldots, 2n-2</math>.
 
The sequence is <math>2, 4, 6, \ldots, 2n-2</math>.
  
−
===Proof===
+
===Proof 1===
 
We will prove that any sequence <math>x_1, \ldots, x_{n-1}</math>, that satisfies
 
We will prove that any sequence <math>x_1, \ldots, x_{n-1}</math>, that satisfies
 
the given conditions, is an
 
the given conditions, is an
Line 53: Line 53:
 
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.
 +
 +
===Proof 2===
 +
Let <math>S=\{x_1,x_2,...,x_{n-1}\}</math>.
 +
Notice that <cmath>x_1<x_1+x_1<x_1+x_2<\dots <x_1+x_{n-2}<2n.</cmath> Then by condition (c), we must have <math>x_1,x_1+x_1,...,x_1+x_{n-2}\in S</math>. This implies that <math>x_1=x_1,x_1+x_1=x_2,...,x_1+x_{n-2}=x_{n-1}</math>, or that <math>x_k=kx_1</math>. Then we have <math>x_1+x_{n-1}=n(x_1)=2n\rightarrow x_1=2</math>, and the rest is trivial.
  
 
==Solution 2==
 
==Solution 2==
Line 65: Line 69:
  
 
==Solution 3==
 
==Solution 3==
−
We will first look at <math>x_1</math> and <math>x_{n-2}</math>. Notice that since <math>x_{n-2}<x_n</math> condition <math>(c)</math> applies to these numbers. Therefore, <math>x_1</math> and <math>x_{n-2}</math> must sum to the only index greater than <math>x_{n-2}</math>, which is <math>x_{n-1} = 2n - x_1</math>. We also know that <math>x_{n-2} = 2n - x_2</math>. Equating, <math>x_1 + 2n - x_2 = 2n - x_1</math> and gives <math>2x_1 = x_2</math>. We can similarly force <math>x_1 + x_{n-3} = x_{n-2}</math> and <math>x_2 + x_{n-3} = x_{n-1}</math>. These both result in <math>3x_1 = x_3</math>. We continue as shown, forcing the first m terms "into" the last m terms. This forms an arithmetic series with common ratio <math>x_1</math> and first term <math>x_1</math>.
+
We can add <math>x_1</math> to every expression in property (a) to get <cmath>2x_1<x_1+x_2<\dots<x_1+x_{n-1}=2n.</cmath> Therefore, we have <math>n-2</math> distinct (because all the <math>x_i</math> are distinct) expressions of the form <math>x_1+x_i</math> for <math>i = 1, 2, \dots n-1</math> that are all less than <math>2n</math>, which means these <math>n-2</math> expressions are also equal to some <math>x_k</math>.  
  
−
Therefore, <math>x_{n-1} = 2n - x_1 = (n-1)x_1</math>. Taking the last equality and simplifying, we get <math>x_1 = 2</math>. So the sequence is <math>2, 4, 6, ... 2n-2</math>. ~Leonard_my_dude~
+
Now, we have that the <math>x_i</math> are all positive, so <math>x_1>0</math>. Adding <math>x_1</math> to both sides, <math>2x_1>x_1</math>. Therefore, since the <math>n-2</math> expressions are all at least <math>2x_1</math>, they have to be equal to <math>x_2, x_3, \dots, x_{n-1}</math>.
  
 +
Since there are <math>n-2</math> distinct expressions <math>x_1+x_i</math> equal to <math>n-2</math> distinct expressions <math>x_j</math>, we have that each <math>x_1+x_i</math> is equal to one <math>x_j</math>. Using the orders of the <math>x_1+x_i</math> and the <math>x_j</math>, we find that
 +
<cmath>\begin{align*}
 +
x_1+x_1 &= x_2 \\
 +
x_1+x_2 &= x_3 \\
 +
...& \\
 +
x_1+x_{n-2} &= x_{n-1}.
 +
\end{align*}</cmath>
 +
This gives us
 +
<cmath>\begin{align*}
 +
x_1 &= x_1 \\
 +
x_2 &= 2x_1 \\
 +
x_3 &= 3x_1 \\
 +
&\text{ }...\\
 +
x_{n-1} &= (n-1)x_1\\
 +
\end{align*}</cmath>
 +
Now, we can use property (b) with <math>i=1</math>, so <math>x_1 + x_{n-1} = 2n</math>, which means <math>x_1 = 2</math>. This gives the sequence <cmath>\boxed{2, 4, 6, \dots, 2(n-1)}</cmath>
 +
-sixeoneeight
 
== See Also ==
 
== See Also ==
 
{{USAJMO newbox|year=2010|num-b=1|num-a=3}}
 
{{USAJMO newbox|year=2010|num-b=1|num-a=3}}

Latest revision as of 22:09, 20 November 2022

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 1

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.

Proof 2

Let $S=\{x_1,x_2,...,x_{n-1}\}$. Notice that \[x_1<x_1+x_1<x_1+x_2<\dots <x_1+x_{n-2}<2n.\] Then by condition (c), we must have $x_1,x_1+x_1,...,x_1+x_{n-2}\in S$. This implies that $x_1=x_1,x_1+x_1=x_2,...,x_1+x_{n-2}=x_{n-1}$, or that $x_k=kx_1$. Then we have $x_1+x_{n-1}=n(x_1)=2n\rightarrow x_1=2$, and the rest is trivial.

Solution 2

The claim is that in this sequence, if there are $2$ elements $a,b$ where $a,b<n$, such that $\gcd(a,b)=1$, then the sequence contains every number less than $2n$.

Proof: Let $a$ and $b$ be the numbers less than $n$ such that $\gcd(a,b)=1$. We take this sequence modulo $n$. This means that if $x_i$ is an element in this sequence then $-x_i$ is as well. $a,b,2n-a,2n-b$ are all elements in the sequence. Clearly, one of $2n-a+b$ and $2n-b+a$ is less than $2n$, which means that $\pm (a-b)$ are in this sequence modulo $n$. Now we want to show every number is achievable. We have already established that $a$ and $b$ are relatively prime, so by euclidean algorithm, if we take the positive difference of $a'$ and $b'$ every time, we will get that $1$ is in our sequence. Then, we can simply add or subtract $1$ as many times from $a$ as desired to get every single number.

We have proved that there are no two numbers that can be relatively prime in our sequence, implying that no two consecutive numbers can be in this sequence. Because our sequence has $n-1$ terms, our sequence must be one of $2,4,6,..,2(n-1)$ or $1,3,5,...$, the latter obviously fails, so $2,4,6...2(n-1)$ is our only possible sequence.

Solution 3

We can add $x_1$ to every expression in property (a) to get \[2x_1<x_1+x_2<\dots<x_1+x_{n-1}=2n.\] Therefore, we have $n-2$ distinct (because all the $x_i$ are distinct) expressions of the form $x_1+x_i$ for $i = 1, 2, \dots n-1$ that are all less than $2n$, which means these $n-2$ expressions are also equal to some $x_k$.

Now, we have that the $x_i$ are all positive, so $x_1>0$. Adding $x_1$ to both sides, $2x_1>x_1$. Therefore, since the $n-2$ expressions are all at least $2x_1$, they have to be equal to $x_2, x_3, \dots, x_{n-1}$.

Since there are $n-2$ distinct expressions $x_1+x_i$ equal to $n-2$ distinct expressions $x_j$, we have that each $x_1+x_i$ is equal to one $x_j$. Using the orders of the $x_1+x_i$ and the $x_j$, we find that \begin{align*} x_1+x_1 &= x_2 \\ x_1+x_2 &= x_3 \\ ...& \\ x_1+x_{n-2} &= x_{n-1}. \end{align*} This gives us \begin{align*} x_1 &= x_1 \\ x_2 &= 2x_1 \\ x_3 &= 3x_1 \\ &\text{ }...\\ x_{n-1} &= (n-1)x_1\\ \end{align*} Now, we can use property (b) with $i=1$, so $x_1 + x_{n-1} = 2n$, which means $x_1 = 2$. This gives the sequence \[\boxed{2, 4, 6, \dots, 2(n-1)}\] -sixeoneeight

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=182719"