Imo 2009 q6

From Polymath Wiki
Revision as of 01:27, 23 July 2009 by Teorth (Talk | contribs)

(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 [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 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]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.


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]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 \lt 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 \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]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

(Insert proof here)

Proof #3

(Insert proof here)