[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 a1, a2, ... , an be distinct positive integers and let M be a set of n − 1 positive integers not containing s = a1 + a2 + ... + an. A grasshopper is to jump along the real axis, starting at the point 0 and making n jumps to the right with lengths a1, a2, ..., an 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 = {b1, b2, ..., bn − 1}, where 0 < b1 < b2 < ... < bn − 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 ai > b1 that doesn't belong to M, then we're done here. This is because placing ai at [0, ai] covers at least one point b1 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 ai. There are 3 possibilities:

  1. an < b1
  2. an = b1
  3. an = bj > b1

We will deal with them in reverse order.

an = bj > b1

Now an = bj is in M, so we proceed from an − 1, an − 2, ... to a1. We stop when we see an ai that's not in M. Let's say we stop at an − 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.

  1. an − k > b1. We're done because of the lemma.
  2. an − k < b1. So |AM| = k > 0, i.e. AM = {an, an − 1, ..., an − k + 1}. This is the most interesting case to me.

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

an = b1

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

an < b1

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

an, as1, as2, ...asn − 1

where s1, ..., sn − 1 is a permutation of {1, ..., n − 1}. Suppose the end points of asj, asj + 1 is b1. Then we could rearrange it as

as1, as2, ..., asj + 1, an, asj + 2, asj + 3...

Because an > asj + 1, b1 is no longer touched by any end point so we're done.

Q.E.D.


post by Shen-Fu Tsai