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]\displaystyle{ a_1, a_2, \ldots, a_n }[/math] be distinct positive integers and let M be a set of [math]\displaystyle{ n-1 }[/math] positive integers not containing [math]\displaystyle{ 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]\displaystyle{ 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 here, and continued 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]\displaystyle{ b_1,\ldots,b_k \in \{a_1,\ldots,a_n\} }[/math] such that [math]\displaystyle{ m = b_1+\ldots+b_k }[/math] and if none of the partial sums [math]\displaystyle{ b_1+\ldots+b_i }[/math] for [math]\displaystyle{ 1 \leq i \leq k }[/math] is a landmine. Thus, our objective is to show that one can safely reach [math]\displaystyle{ a_1+\ldots+a_n }[/math] in n steps.

Proof #1

We induct on n, assuming that $latex n > 2$ 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]\displaystyle{ k \geq 1 }[/math], then we are done by induction hypothesis (removing the steps [math]\displaystyle{ b_1,\ldots,b_k }[/math] from [math]\displaystyle{ a_1,\ldots,a_n }[/math], and shifting the remaining mines leftwards by [math]\displaystyle{ 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]\displaystyle{ k \geq 1 }[/math]. We will refer to this assumption as Assumption A.

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

We say that the grasshopper is immune to order j for some [math]\displaystyle{ 1 \leq j \leq n }[/math] if for every distinct [math]\displaystyle{ b_1,\ldots,b_{j'} }[/math] in [math]\displaystyle{ \{a_1,\ldots,a_n\} }[/math] with [math]\displaystyle{ 1 \leq j' \leq j }[/math] and [math]\displaystyle{ b_1+\ldots+b_{j'} \not \in M }[/math], the grasshopper can safely reach [math]\displaystyle{ b_1+\ldots+b_{j'} }[/math] in j' steps, using a permutation of [math]\displaystyle{ b_1,\ldots,b_{j'} }[/math]. In particular this implies that every integer in [math]\displaystyle{ 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]\displaystyle{ 1 \leq j \lt 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]\displaystyle{ M \cap S_j }[/math] has cardinality at most j. Then the claim is easy, because to reach [math]\displaystyle{ b_1+\ldots+b_{j+1} \in S_{j+1} \backslash M }[/math] in j+1 steps using a permutation of [math]\displaystyle{ b_1+\ldots+b_{j+1} }[/math], there are j+1 points in [math]\displaystyle{ 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]\displaystyle{ M \cap S_j }[/math] has cardinality at least j+1. Then, by Assumption A, we cannot pass [math]\displaystyle{ M \cap S_j }[/math] safely in j+1 or fewer steps. In particular, we cannot safely reach [math]\displaystyle{ a_i+a_{n-j+1}+\ldots+a_n }[/math] in j+1 steps for any [math]\displaystyle{ 1 \leq i \leq n-j }[/math].

Let I be the set of all [math]\displaystyle{ 1 \leq i \leq n-j }[/math] such that [math]\displaystyle{ a_i+a_{n-j+1}+\ldots+a_n }[/math] is not in M. Since [math]\displaystyle{ 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]\displaystyle{ a_i+a_{n-j+1}+\ldots+a_{n-1} }[/math] must lie in M, otherwise we could safely reach [math]\displaystyle{ 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]\displaystyle{ 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

(Insert proof here)

Proof #3

(Insert proof here)