# Imo 2009 q6

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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 $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.

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 $b_1,\ldots,b_k \in \{a_1,\ldots,a_n\}$ such that $m = b_1+\ldots+b_k$ and if none of the partial sums $b_1+\ldots+b_i$ for $1 \leq i \leq k$ is a landmine. Thus, our objective is to show that one can safely reach $a_1+\ldots+a_n$ 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 $k \geq 1$, then we are done by induction hypothesis (removing the steps $b_1,\ldots,b_k$ from $a_1,\ldots,a_n$, and shifting the remaining mines leftwards by $b_1+\ldots+b_k$, 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 $k \geq 1$. We will refer to this assumption as Assumption A.

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

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

Let I be the set of all $1 \leq i \leq n-j$ such that $a_i+a_{n-j+1}+\ldots+a_n$ is not in M. Since $M \cap S_j$ already uses up at least j+1 of the points in M, I cannot be empty. For each i in I, $a_i+a_{n-j+1}+\ldots+a_{n-1}$ must lie in M, otherwise we could safely reach $a_i+a_{n-j+1}+\ldots+a_n$ in j+1 steps by Assumption A. Similarly, if i is the smallest element of I, $a_i+a_{n-j+1}+\ldots+a_n - a_m$ 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)