# Difference between revisions of "Imo 2009 q6"

(→Proof #4) |
|||

Line 171: | Line 171: | ||

There is a dual form of Bramm’s proof. It is based on the fact that we can subtract everything from the sum of the a_i’s and get a copy of the same problem with roughly what happens is that you can replace max a with target-max a and let f be the number of mines target-max a and target. I think that most proofs have a dual associated with them. | There is a dual form of Bramm’s proof. It is based on the fact that we can subtract everything from the sum of the a_i’s and get a copy of the same problem with roughly what happens is that you can replace max a with target-max a and let f be the number of mines target-max a and target. I think that most proofs have a dual associated with them. | ||

− | |||

− | |||

Here is case one of the dual: Max a is a mine and f is greater 0. In that case, out of the target-a_i that are not max a (n numbers), at least n-f are not mined (when taken as a first jump). Consider the n double jumps (target–max a_i != max a, target-max a, target). At least n-f of those are not mined on the last jump. The number of mines in (0 target -max a) is the number of mines (n) less f less the one for target -max a, yielding n-f-1 which is less than n-f. Thus by counting argument, at least one of the double jumps does not hit a mine on both jumps. This double jump takes two jumps and jumps over f+1 >=2 mines, yielding a problem with n-2 mines and n-1 remaining jumps, which is solved by induction. | Here is case one of the dual: Max a is a mine and f is greater 0. In that case, out of the target-a_i that are not max a (n numbers), at least n-f are not mined (when taken as a first jump). Consider the n double jumps (target–max a_i != max a, target-max a, target). At least n-f of those are not mined on the last jump. The number of mines in (0 target -max a) is the number of mines (n) less f less the one for target -max a, yielding n-f-1 which is less than n-f. Thus by counting argument, at least one of the double jumps does not hit a mine on both jumps. This double jump takes two jumps and jumps over f+1 >=2 mines, yielding a problem with n-2 mines and n-1 remaining jumps, which is solved by induction. |

## Revision as of 16:19, 23 July 2009

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.

## Contents

## 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 \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

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

A variant of Proof #2, with fewer cases (2!) and a bit more formally presented.

### Generalisation

Given a starting point [math]a_{0}[/math], [math]n[/math] distinct positive integers, [math]A={a_{1},a_{2},...,a_{n}}[/math] and [math]k[/math] values [math]M={m_{1},m_{2},...,m_{k}}[/math] with [math]k\ltn[/math], where [math]a_{0}\notin M[/math] and [math]\sum_{i=0}^{n}a_{i}\notin M[/math], then there is an ordering, [math]\phi[/math], on [math]A[/math], such that [math]a_{0}+\sum_{i=1}^{j}a_{\phi(i)}\notin M[/math] for any [math]j[/math] between [math]1[/math] and [math]n[/math].

### Base Case

If [math]n=1[/math] then [math]k=0[/math], and [math]M[/math] is the empty set and theorem is trivially true.

### Inductive Step

When [math]n\gt1[/math], then either [math]k=0[/math], [math]M[/math] is the empty set, and hypothesis is trivially true, or [math]k\gt0[/math]. Assume hypothesis is true for all [math]n'\ltn[/math], and [math]k'\ltk[/math]. Label A so that [math]a_{n}=max(A)[/math], and M so that [math]m_{1}=min(M)[/math].

#### Case 1

Assume: [math]a_{0}+a_{n}\leq m_{1}[/math] or [math]a_{0}+a_{n}\notin M[/math]

In this case [math]a_{0}+a_{n}\notin M\setminus\{m_{1}\}[/math], so by the inductive hypothesis, it is possible to find an ordering for [math]A'=A\setminus\{a_{n}\}[/math], [math]M'=M\setminus\{m_{1}\}[/math], [math]a'_{0}=a_{0}+a_{n}[/math]. Call that ordering [math]\phi'[/math].

Consider the mapping [math]\phi(1)=n[/math], and [math]\phi(x)=\phi'(x-1)[/math] when [math]x\geq2[/math]. Then we have that [math]a'_{0}+\sum_{i=1}^{j}a_{\phi'(i)}\notin M'[/math] for [math]1\leq j\leq n-1[/math], which is the same as [math]a_{0}+a_{n}+\sum_{i=2}^{j}a_{\phi(i)}\notin M\setminus\{m_{1}\}[/math] for [math]2\leq j\leq n[/math], and since [math]a_{0}+a_{n}\notin M\setminus\{m_{1}\}[/math] and [math]a_{\phi(1)}=a_{n}[/math], we have [math]a_{0}+\sum_{i=1}^{j}a_{\phi(i)}\notin M\setminus\{m_{1}\}[/math] for [math]1\leq j\leq n[/math].

Next consider the partial sums, [math]s_{j}=a_{0}+\sum_{i=1}^{j}a_{\phi(i)}[/math]. Since [math]a_{\phi(i)}[/math] is a positive integer, [math]s_{j}\lts_{j+1}[/math], so there exists some [math]\gamma\in\{0\ldots n\}[/math] such that [math]s_{j}\leq m_{1}[/math] when [math]j\lt\gamma[/math], and [math]m_{1}\lts_{j}[/math] when [math]\gamma\leq j[/math].

Now consider the reordering

[math] \rho(x)=\begin{cases} \phi(x+1) & 1\leq x\lt\gamma\\ \phi(0) & x=\gamma\\ \phi(x) & \gamma\ltx \end{cases} [/math]

and the corresponding partial sums [math]s'_{j}=a_{0}+\sum_{i=1}^{j}a_{\rho(i)}[/math].

Consider [math]j\leq\gamma[/math]. Then [math]s'_{j}=s_{j}-a_{\phi(0)}+a_{\rho(j)}=s_{j}-a_{n}+a_{\phi(\gamma)}[/math]. And since [math]a_{n}=max(A)[/math], we have [math]s'_{j}\lts_{j}\leq m_{1}[/math], and hence [math]s'_{j}\notin M[/math].

Further, for [math]\gamma\leq j[/math], we have [math]s'_{j}=s_{j}[/math], and since [math]m_{1}\lts_{j}[/math] and [math]s_{j}\notin M\setminus\{m_{1}\}[/math], we have [math]s'_{j}\notin M[/math] in all cases, and our ordering, [math]\rho[/math] suffices.

#### Case 2

Assume: [math]m_{1}\lta_{0}+a_{n}[/math] and [math]a_{0}+a_{n}\in M[/math]

In this case we first observe that [math]m_{1}[/math] and [math]a_{0}+a_{n}[/math] are distinct members of [math]M[/math], and thus [math]k\geq2[/math] and [math]n\geq3[/math].

We consider [math]n-1[/math] pigeon holes labelled [math]1\leq i\ltn[/math], assigning each element [math]m\in M[/math] to a pigeon hole if either [math]m=a_{0}+a_{i}[/math] or [math]m=a_{0}+a_{i}+a_{n}[/math]. Since each [math]a_{i}[/math] is distinct and positive and [math]a_{i}\lta_{n}[/math], no[math]m[/math] can be assigned to two different pigeon holes, and furthermore, since [math]a_{0}+a_{n}\in M[/math] only the remaining [math]k-1[/math] members of [math]M[/math] can be assigned to a pigeon-hole.

But since [math]k\ltn[/math], [math]k-1\ltn-1[/math], and at least one pigeon-hole must be empty, so call it [math]x[/math]. This means [math]a_{0}+a_{x}[/math] and [math]a_{0}+a_{x}+a_{n}[/math] are not members of [math]M[/math], and by the inductive hypothesis, we can find an ordering [math]\phi'[/math] for [math]A'=A\setminus\{a_{x},a_{n}\}[/math], [math]M'=M\setminus\{m_{1},a_{0}+a_{n}\}[/math], [math]a'_{0}=a_{0}+a_{x}+a_{n}[/math], and establish an ordering that satisfies the requirements:

[math]\phi(j)=\begin{cases} x & j=1\\ n & j=2\\ \phi'(j-2) & j\gt2 \end{cases} [/math]

## Proof #4

There is a dual form of Bramm’s proof. It is based on the fact that we can subtract everything from the sum of the a_i’s and get a copy of the same problem with roughly what happens is that you can replace max a with target-max a and let f be the number of mines target-max a and target. I think that most proofs have a dual associated with them.

Here is case one of the dual: Max a is a mine and f is greater 0. In that case, out of the target-a_i that are not max a (n numbers), at least n-f are not mined (when taken as a first jump). Consider the n double jumps (target–max a_i != max a, target-max a, target). At least n-f of those are not mined on the last jump. The number of mines in (0 target -max a) is the number of mines (n) less f less the one for target -max a, yielding n-f-1 which is less than n-f. Thus by counting argument, at least one of the double jumps does not hit a mine on both jumps. This double jump takes two jumps and jumps over f+1 >=2 mines, yielding a problem with n-2 mines and n-1 remaining jumps, which is solved by induction.

Here is case two of the dual: Target-max a is not a mine and f>0. Take max a as last jump, yielding problem with n remaining jumps and n-f<n mines, which is solved by induction.

Here is case three of the dual: Target- max a is a mine and f=0. Let max M be the largest mine in M. Construct M’=M\{max M}. Jump target-max a to target as the last jump and solve the n-problem with the remaining a_i and M’ Let a_x be the last jump of this solution. Exchange max a and a_x (i.e. jump a_x last and max a before that). target -(max a+a_x) is no mine (guaranteed by solution), target-a_x is no mine (because target-a_x is greater than target-max a == max M as above). There are no mines in the rest. We have completed solution for n+1.

Here is the final case of the dual: Target-max a is not a mine and f=0. As in case 3, construct M’, jump max a last and solve for the remaining a_i and M’. If this solution hits max M in step k, construct a new solution by exchanging step k-1 and the last step (i.e. target-max a). There are no mines after max M, thus the mine is avoided and no new mines are hit. We have completed solution for n+1

## Proof #5

(Insert proof here)