[Math] The infamous Grasshopper problem

This is one of the hardest problems in IMO history. As regulated by IMO rules, it permits solutions involving only elementary techniques. My solution is very similar to the official one.

The infamous Grasshopper problem

Let a₁, a₂, ... , a_n be distinct positive integers and let M be a set of n − 1 positive integers not containing s = a₁ + a₂ + ... + 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₁, a₂, ..., 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.

Proof

First note that the statement is still equivalent if |M| < n.

Let the set M = {b₁, b₂, ..., b_n − 1}, where 0 < b₁ < b₂ < ... < b_n − 1 < s. We will prove by induction on n. n = 1 and n = 2 are trivial. Suppose the statement holds for all n ≤ m. We want to prove that it holds for n = m + 1 ≥ 3.

Lemma

If there's any a_i > b₁ that doesn't belong to M, then we're done here. This is because placing a_i at [0, a_i] covers at least one point b₁ in M, and there are now n − 1 segments and less than n − 1 points left, so by induction the statement holds.

So suppose there isn't such a_i. There are 3 possibilities:

a_n < b₁

a_n = b₁

a_n = b_j > b₁

We will deal with them in reverse order.

a_n = b_j > b₁

Now a_n = b_j is in M, so we proceed from a_n − 1, a_n − 2, ... to a₁. We stop when we see an a_i that's not in M. Let's say we stop at a_n − k with k > 0. Note we will stop at some point because in A there can be at most |M| = n − 1 numbers in M.

a_n − k > b₁. We're done because of the lemma.

a_n − k < b₁. So |A∩M| = k > 0, i.e. A∩M = {a_n, a_n − 1, ..., a_{n − k + 1}}. This is the most interesting case to me.

How many points in M are larger than a_n? At most n − 1 − k because k of them are in the intersection of M and A. How many a_i in A are less than b₁? n − k. Therefore, there is at least an a_i < b₁ such that a_i + a_n is not in M. If we put a_i at [0, a_i] and a_n at [a_i, a_i + a_n], we're sure these two segments have no end points in M because a_i < b₁ and a_i + a_n is not in M, yet they cover at least 2 points in M, i.e. b₁ and a_n = b_j. By induction, the remaining n − 2 ≥ 1 segments can be arranged such that no end points fall into M.

a_n = b₁

Place a_n at [0, a_n]. Let A’ = A − {a_n} and M’ = M − {b₁}. By induction we can arrange A’ in such a way that no points in M’ coincide with an end point in A’. Now only b₁ touches end points of a_n and a_j. Since a_j < a_n, swapping a_j and a_n resolves it.

a_n < b₁

This is similar. Let's put a_n at the [0, a_n]. There are n − 1 segments but n − 1 points left, so let's pretend b₁ doesn't exist. That is, consider M’ = M − {b₁}. Now by induction we can arrange the remaining n − 1 segments such that no point in M’ is touched by any end point. Only b₁ might coincide with an end point of A − {a_n}. Let's assume the current arrangement is

a_n, a_s₁, a_s₂, ...a_{s_n − 1}

where s₁, ..., s_n − 1 is a permutation of {1, ..., n − 1}. Suppose the end points of a_{s_j}, a_{s_j + 1} is b₁. Then we could rearrange it as

a_s₁, a_s₂, ..., a_{s_j + 1}, a_n, a_{s_j + 2}, a_{s_j + 3}...

Because a_n > a_{s_j + 1}, b₁ is no longer touched by any end point so we're done.

Q.E.D.

post by Shen-Fu Tsai