Difference between revisions of "2009 IMO Problems/Problem 6"

Latest revision as of 00:18, 19 November 2023

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.

@@ Line 5: / Line 5: @@
 ''Author: Dmitry Khramtsov, Russia''
-== Solution 1==
+== 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>.
@@ Line 32: / Line 32: @@
 Since we have an induction on <math>n</math>, the statement must be true for all <math>n</math>, and we are done.
-==Solution 2==
-This solution will use induction rather than strong induction; as a result, it will be less rigorous.
-We proceed as the above step to prove that the grasshopper succeeds for <math>n = 1</math> and <math>n = 2</math>. We now assume that the grasshopper succeeds for <math>n</math>, and we are to prove that it still succeeds for <math>n + 1</math>. Let us call the grasshopper's "trajectory" as the path it takes with <math>n</math> elements to never land on a point in <math>M</math>. We are now going to add <math>a_{n + 1}</math> the grasshopper can make and another point to <math>M</math> to prove that the grasshopper wins for <math>n + 1</math>. There are 4 cases for where this last point to <math>M</math> could be. We will denote this point as <math>P</math>.
-'''Case 1:''' <math>P</math> is not along the trajectory of the grasshopper. In this case, the grasshopper can make the jump of <math>a_{n + 1}</math> after completing its trajectory, since it will not land on <math>P</math>. Since <math>P</math> cannot be equal to <math>s</math>, we do not have to worry if the <math>n + 1th</math> jump lands on <math>P</math>.
-'''Case 2:''' <math>P</math> is along the trajectory of the grasshopper. Now, we analyze where along this trajectory <math>P</math> is. We will now attempt to prove that it is possible to change the path the grasshopper takes to avoid <math>P</math>. Assume <math>P</math> is the point the grasshopper reaches after <math>k</math> jumps. The worst-case scenario would be that all of the points of <math>M</math> block a combination of <math>k</math> jumps. Since no point of <math>M</math> can be at the origin or be equal to <math>s</math>, we have that <math>0 < k < n + 1</math>. The number of combinations of <math>k</math> jumps would be <math>{n + 1}\choose{k}</math>, which always exceeds the number of points in <math>M</math>, since the smallest value, where <math>k = 1</math>, results in <math>n + 1</math> combinations, but <math>M</math> has only <math>n</math> points and thus <math>n</math> combinations to prevent.
 == See Also ==
-{{IMO box|year=1959|num-b=1|num-a=3}}
+{{IMO box|year=2009|num-b=5|after=Last Problem}}
 [[Category:Olympiad Algebra Problems]]

2009 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last Problem
All IMO Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "2009 IMO Problems/Problem 6"

Latest revision as of 00:18, 19 November 2023

Problem

Solution

See Also