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 "2009 IMO Problems/Problem 6"

m
Line 4: Line 4:
  
 
''Author: Dmitry Khramtsov, Russia''
 
''Author: Dmitry Khramtsov, Russia''
 +
 +
== Solution ==
 +
 +
We will use strong induction on <math>n</math>. When <math>n = 1</math>, there are no elements in <math>M</math>, so the one jump can be made without landing on a point in <math>M</math>. When <math>n = 2</math>, we consider two cases. If <math>a_1</math> is not in <math>M</math>, then the order <math>a_1, a_2</math> will work. If <math>a_1</math> is in <math>M</math>, then <math>a_2</math> is not in <math>M</math> and the order <math>a_2, a_1</math> will work. We will assume that the order can be chosen in such a way for all integers <math>n < k</math> for <math>k \ge 3</math>.
 +
 +
When <math>n = k</math>, we can assume WLOG that <math>a_1<a_2< \ldots <a_k</math>. We can also assume that the elements of <math>M</math> are distinct, since if two elements are identical, we can treat them as one and use induction on <math>n = k-1</math>. We now consider four cases:
 +
 +
 +
'''Case 1:''' <math>a_k</math> is in <math>M</math> but <math>a_1, a_2, \ldots, a_{k-1}</math> are not.
 +
 +
There are at most <math>k-2</math> elements in <math>M</math> greater than <math>a_k</math>. Then, from our assumption, there exists an order of jumps starting from <math>a_k</math> of lengths <math>a_1, a_2, \ldots, a_{k-1}</math> where the first jump is <math>a_i</math> such that the grasshopper will not land in any point in <math>M</math>. We can then switch the jumps <math>a_k</math> and <math>a_i</math>. Since <math>a_i</math> is not in <math>M</math> and no subsequent jumps result in the grasshopper landing in a point in <math>M</math>, this sequence is valid.
 +
 +
'''Case 2:''' <math>a_k</math> is not in <math>M</math> but at least one of <math>a_1, a_2, \ldots, a_{k-1}</math> is.
 +
 +
There are at most <math>k-2</math> elements in <math>M</math> greater than <math>a_k</math>. Then, from our assumption, there exists an order of jumps starting from <math>a_k</math> of lengths <math>a_1, a_2, \ldots, a_{k-1}</math> such that the grasshopper will not land in any point in <math>M</math>. Adding <math>a_k</math> at the beginning of this sequence then results in a valid sequence.
 +
 +
'''Case 3:''' <math>a_k</math> is in <math>M</math> and at least one of <math>a_1, a_2, \ldots, a_{k-1}</math> is.
 +
 +
Consider the following pairs of distinct integers <math>(a_1, a_1+a_k), (a_2, a_2+a_k), \ldots, (a_{k-1}, a_{k-1}+a_k)</math>. Since at most <math>k-2</math> of these points are in <math>M</math>, by the pigeonhole principle, there exists an integer <math>i</math> such that <math>a_i, a_i + a_k</math> are both not in <math>M</math>. Since there are at most <math>k-3</math> elements greater than <math>a_k</math>, at most <math>k-3</math> elements are greater than <math>a_i + a_k</math>. Then, from our assumption, there exists an order of jumps starting from <math>a_i + a_k</math> of lengths <math>a_1, a_2, \ldots, a_{i-1}, a_{i+1}, \ldots, a_{k-1}</math> such that the grasshopper will not land in any point in <math>M</math>. Adding <math>a_i, a_k</math> at the beginning of this sequence then results in a valid sequence.
 +
 +
'''Case 4:''' None of <math>a_1, a_2, \ldots, a_k</math> are in <math>M</math>.
 +
 +
Assume that there exists no valid sequence - that any order of jumps will result in the grasshopper landing on at least one element in <math>M</math>. We can select any element <math>m_i</math> in <math>M</math> and, from our assumption, construct a sequence beginning at some <math>a_j</math> containing <math>n-1</math> jumps <math>a_1, a_2, \ldots, a_{j-1}, a_{j+1}, \ldots, a_k</math> that will not land on any of the other <math>n-2</math> elements in <math>M</math>. Since no valid sequence exists, during this sequence of jumps, the grasshopper must land on <math>m_i</math>.
 +
 +
WLOG, we let <math>m_1 < m_2 < \ldots < m_{k-1}</math>. We let <math>i = 1</math> and <math>j = k</math> and use the corresponding sequence that only lands on <math>m_1</math> and no other element in <math>M</math>. Let the jump immediately after landing on <math>m_1</math> be <math>a_x</math>, where <math>x < n</math>. We swap jumps <math>a_x</math> and <math>a_n</math>. Now, since <math>a_n > a_x</math>, all jumps before <math>a_n</math> will land on a integer less than <math>m_1</math>. Since <math>m_1</math> is the smallest element in <math>M</math>, none of the jumps before <math>a_n</math> will land on a point in <math>M</math>. Since no jumps after <math>a_n</math> will land on an element in <math>M</math> by the construction, the grasshopper must then land on an element <math>m_y > m_1</math> in <math>M</math> after making the jump <math>a_n</math>. However, this would imply that the original construction would land on another element <math>m_y</math> different from <math>m_1</math>, but this is a contradiction. So, a valid sequence must exist.
 +
 +
 +
Since we have an induction on <math>n</math>, the statement must be true for all <math>n</math>, and we are done.

Revision as of 17:10, 26 September 2013

Problem

Let $a_1,a_2,\ldots,a_n$ be distinct positive integers and let $M$ be a set of $n-1$ positive integers not containing $s=a_1+a_2+\ldots+a_n$. A grasshopper is to jump along the real axis, starting at the point $0$ and making $n$ jumps to the right with lengths $a_1,a_2,\ldots,a_n$ in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in $M$.

Author: Dmitry Khramtsov, Russia

Solution

We will use strong induction on $n$. When $n = 1$, there are no elements in $M$, so the one jump can be made without landing on a point in $M$. When $n = 2$, we consider two cases. If $a_1$ is not in $M$, then the order $a_1, a_2$ will work. If $a_1$ is in $M$, then $a_2$ is not in $M$ and the order $a_2, a_1$ will work. We will assume that the order can be chosen in such a way for all integers $n < k$ for $k \ge 3$.

When $n = k$, we can assume WLOG that $a_1<a_2< \ldots <a_k$. We can also assume that the elements of $M$ are distinct, since if two elements are identical, we can treat them as one and use induction on $n = k-1$. We now consider four cases:


Case 1: $a_k$ is in $M$ but $a_1, a_2, \ldots, a_{k-1}$ are not.

There are at most $k-2$ elements in $M$ greater than $a_k$. Then, from our assumption, there exists an order of jumps starting from $a_k$ of lengths $a_1, a_2, \ldots, a_{k-1}$ where the first jump is $a_i$ such that the grasshopper will not land in any point in $M$. We can then switch the jumps $a_k$ and $a_i$. Since $a_i$ is not in $M$ and no subsequent jumps result in the grasshopper landing in a point in $M$, this sequence is valid.

Case 2: $a_k$ is not in $M$ but at least one of $a_1, a_2, \ldots, a_{k-1}$ is.

There are at most $k-2$ elements in $M$ greater than $a_k$. Then, from our assumption, there exists an order of jumps starting from $a_k$ of lengths $a_1, a_2, \ldots, a_{k-1}$ such that the grasshopper will not land in any point in $M$. Adding $a_k$ at the beginning of this sequence then results in a valid sequence.

Case 3: $a_k$ is in $M$ and at least one of $a_1, a_2, \ldots, a_{k-1}$ is.

Consider the following pairs of distinct integers $(a_1, a_1+a_k), (a_2, a_2+a_k), \ldots, (a_{k-1}, a_{k-1}+a_k)$. Since at most $k-2$ of these points are in $M$, by the pigeonhole principle, there exists an integer $i$ such that $a_i, a_i + a_k$ are both not in $M$. Since there are at most $k-3$ elements greater than $a_k$, at most $k-3$ elements are greater than $a_i + a_k$. Then, from our assumption, there exists an order of jumps starting from $a_i + a_k$ of lengths $a_1, a_2, \ldots, a_{i-1}, a_{i+1}, \ldots, a_{k-1}$ such that the grasshopper will not land in any point in $M$. Adding $a_i, a_k$ at the beginning of this sequence then results in a valid sequence.

Case 4: None of $a_1, a_2, \ldots, a_k$ are in $M$.

Assume that there exists no valid sequence - that any order of jumps will result in the grasshopper landing on at least one element in $M$. We can select any element $m_i$ in $M$ and, from our assumption, construct a sequence beginning at some $a_j$ containing $n-1$ jumps $a_1, a_2, \ldots, a_{j-1}, a_{j+1}, \ldots, a_k$ that will not land on any of the other $n-2$ elements in $M$. Since no valid sequence exists, during this sequence of jumps, the grasshopper must land on $m_i$.

WLOG, we let $m_1 < m_2 < \ldots < m_{k-1}$. We let $i = 1$ and $j = k$ and use the corresponding sequence that only lands on $m_1$ and no other element in $M$. Let the jump immediately after landing on $m_1$ be $a_x$, where $x < n$. We swap jumps $a_x$ and $a_n$. Now, since $a_n > a_x$, all jumps before $a_n$ will land on a integer less than $m_1$. Since $m_1$ is the smallest element in $M$, none of the jumps before $a_n$ will land on a point in $M$. Since no jumps after $a_n$ will land on an element in $M$ by the construction, the grasshopper must then land on an element $m_y > m_1$ in $M$ after making the jump $a_n$. However, this would imply that the original construction would land on another element $m_y$ different from $m_1$, but this is a contradiction. So, a valid sequence must exist.


Since we have an induction on $n$, the statement must be true for all $n$, and we are done.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_IMO_Problems/Problem_6&oldid=57160"