Problem 6

Let

a_1,\ldots,a_n

be distinct positive integers and let

M

be a set of

n-1

positive integers not containing

s=a_1+\cdots+a_n

. A grasshopper starts at

0

and makes

n

jumps to the right, with lengths

a_1,\ldots,a_n

in some order. Prove that the order can be chosen so that the grasshopper never lands on a point in

M

Step 2 of 5: A safe checkpoint with a mine to its right

Previous step Next step

In plain words

A mine beyond the checkpoint leaves too few mines before it to obstruct the shorter jumps.

x\notin M,\quad M\cap(x,\infty)\ne\varnothing

Detailed analysis

Suppose $x\notin M$ and $M\cap(x,\infty)\ne\varnothing$ . At most $n-2$ forbidden points lie at or below $x$ . Apply the induction hypothesis to the $n-1$ lengths $a_1,\ldots,a_{n-1}$ and those points, reaching $x$ without a hit. The final jump $a_n$ lands at $x+a_n=s$ , which is not in $M$ .