View source for Imo 2009 q6

The International Mathematical Olympiad (IMO) consists of a set of six problems, to be solved in two sessions of four and a half hours each.  Traditionally, the last problem (Problem 6) is significantly harder than the others.  Problem 6 of the 2009 IMO, which was given out on July 16, reads as follows:

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

A collaborative effort to study this problem was formed [http://terrytao.wordpress.com/2009/07/20/imo-2009-q6-as-a-mini-polymath-project/ here], and continued [http://terrytao.wordpress.com/2009/07/21/imo-2009-q6-mini-polymath-project-cont/ here].

This page is a repository for any text related to this project, for instance proofs of this problem.

== Notation ==

Elements of M will be referred to as "landmines".

We say that an integer m can be ''safely reached in k steps'' if there exist distinct <math>b_1,\ldots,b_k \in \{a_1,\ldots,a_n\}</math> such that <math>m = b_1+\ldots+b_k</math> and if none of the partial sums <math>b_1+\ldots+b_i</math> for <math>1 \leq i \leq k </math> is a landmine.  Thus, our objective is to show that one can safely reach <math>a_1+\ldots+a_n</math> in n steps.

In proof 2 I have used 'mines'. I refer to the possibilities for the grasshopper as leaps, and to the actual components of a path through the minefield as jumps. So the longest leap can be the first or second or third jump (etc). I refer to an unmined space as a 'clear space'. Please feel free to suggest better terms/edit for consistency.

== Proof #1 ==

We induct on n, assuming that <math>n \geq 3</math> and that the claim has already been proven for smaller n.

Observe that if one can pass k or more mines safely in k steps for some <math>k \geq 1</math>, then we are done by induction hypothesis (removing the steps <math>b_1,\ldots,b_k</math> from <math>a_1,\ldots,a_n</math>, and shifting the remaining mines leftwards by <math>b_1+\ldots+b_k</math>, reducing n by k, and adding dummy mines if necessary.  Thus we may assume that it is not possible to pass k or more mines safely in k steps for any <math>k \geq 1</math>.  We will refer to this assumption as '''Assumption A'''.

For each <math>1 \leq j \leq n</math>, let <math>S_j</math> denote the set of integers formed by summing j distinct elements from <math>a_1,\ldots,a_n</math>.  Thus for instance <math>S_1 = \{a_1,\ldots,a_n\}</math>, <math>S_2 = \{a_i+a_{i'}: 1 \leq i < i' \leq n</math>, and <math>S_n = \{a_1+\ldots+a_n\}</math>.

We say that the grasshopper is ''immune to order j'' for some <math>1 \leq j \leq n</math> if for every distinct <math>b_1,\ldots,b_{j'}</math> in <math>\{a_1,\ldots,a_n\}</math> with <math>1 \leq j' \leq j</math> and <math>b_1+\ldots+b_{j'} \not \in M</math>, the grasshopper can safely reach <math>b_1+\ldots+b_{j'}</math> in j' steps, using a permutation of <math>b_1,\ldots,b_{j'}</math>.  In particular this implies that every integer in <math>S_j \backslash M</math> can be safely reached in j steps.  Clearly the grasshopper is immune to order 1; it will suffice to show that the grasshopper is immune to order n.

We use induction.  Let <math>1 \leq j < n</math>, and suppose that the grasshopper is already known to be immune to order 1.  We now show that it is immune to order j+1.

First suppose that <math>M \cap S_j</math> has cardinality at most j.  Then the claim is easy, because to reach <math>b_1+\ldots+b_{j+1} \in S_{j+1} \backslash M</math> in j+1 steps using a permutation of <math>b_1+\ldots+b_{j+1}</math>, there are j+1 points in <math>S_j</math> that one could potentially use.  At most j of these lie in M, so there is one that does not lie in M.  By induction hypothesis, the grasshopper can reach that point safely in j steps, and can thus reach the original point in j+1 steps, as required.

Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1.  Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps.  In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.  

Let I be the set of all <math>1 \leq i \leq n-j</math> such that <math>a_i+a_{n-j+1}+\ldots+a_n</math> is not in M.  Since <math>M \cap S_j</math> already uses up at least j+1 of the points in M, I cannot be empty.  For each i in I, <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> must lie in M, otherwise we could safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps by Assumption A.  Similarly, if i is the smallest element of I, <math>a_i+a_{n-j+1}+\ldots+a_n - a_m</math> must lie in M for any m equal to either i or n-j+1,...,n-1.  But this forces M to contain n distinct elements, a contradiction.

== Proof #2 ==

This is a version of Brumm’s proof with inspiration from Curioso.
It is another induction, assuming we can deal with n-1 mines in n leaps, and extending to the case with n mines and n+1 leaps.
This is an attempt at a write-up with minimal technicality - it is therefore a little wordy.
The basic strategy is to try to make the longest leap and see what might go wrong.
It turns out that there are two things.

First, we might not jump any mines at all (but perhaps landing on a mine), so our inductive hypothesis has to deal with too many mines.
In fact we can deal with all but one of the mines. We start from the far end and trace a path backwards, keeping the longest leap in reserve, and knowing that all the mines are in the range of the remaining leaps, because we didn't jump any with the longest leap. We can arrange for the mine we can't pass to be the one the one closest to the beginning and then swap in the longest leap to make sure we can jump this one as well.

Second, we might land on a mine and jump some too. The mines we jump might get in the way of shorter leaps.
It turns out that we can always find two leaps, with the longest leap as the second jump, taking us beyond at least two mines and the induction goes through.


'''PROOF'''

We can trivially negotiate zero mines with one leap (the case n=1).

We assume that, provided the last place is clear, that we can deal with (n-1) or fewer mines in n leaps, and we want to show that we can deal with n mines in (n+1) leaps.

We try to make the longest leap.


Case 1: If the longest leap carries us to a clear space (no mine) and jumps at least one mine, we are left with n leaps and at most (n-1) mines, which we can do by hypothesis.


Case 2: If the longest leap carries us to a clear space, but doesn’t jump a mine, we work from the other end of the minefield. If we remove the mine closest to the beginning we have (n-1) mines left, and we know that we can negotiate all of these with the n leaps other than the largest (we ignore the blank spaces covered by the largest leap at the beginning).

Case 2.1: If this arrangement also avoids the mine we removed, we are done. 

Case 2.2: If it doesn’t – working from the far end – take the leap which lands on this mine, and replace it by the longest leap, which is longer, and therefore jumps us clear of the mine. There are no mines closer to the beginning than this, so we use any remaining leaps to take us to the beginning and we have a path through.


Case 3: If the longest leap lands on a mine but doesn’t jump any mines, this is similar to case 2.2 – this mine is the closest one to the beginning. We can find a path from the far end which lands only on this mine (by hypothesis - jumping the remaining n-1 mines with n leaps). We look at the leap which takes us there, and swap it with the longest leap to jump clear of it, while the swapped leap takes us to the beginning, and we have our path.


Case 4: In this case the longest leap lands on a mine and jumps one or more mines. 
Following brumm’s notation, assume the longest leap jumps f of the mines, with f at least 1.
We have accounted for f+1 mines (including the one we landed on). So there are (n-f-1) mines out of range of the longest leap.
Observe that there are n other possible leaps from the beginning, all different and shorter than the longest leap, and there are at most f mines in this range to hit, so there are at least (n-f) possible initial leaps which don’t hit a mine.
For each of those (n-f) possible first leaps, try following with the longest leap, which definitely takes us beyond the first f+1 mines. This gives us (n-f) double jumps of different lengths, but there are just (n-f-1) mines we might hit, so one of these double jumps lands clear.
This double jump passes at least two mines. So the remaining (n-1) jumps are available to negotiate at most (n-2) mines, and we are done.

== Proof #3 ==

(Insert proof here)