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 3 of 5: Replace a jump that hits the last remaining mine

Previous step Next step

In plain words

If the checkpoint has no mine to its right, the longest jump can jump over the largest mine whenever the shorter path reaches it.

m=\max M\quad\Longrightarrow\quad m-a_k+a_n>m

Detailed analysis

First suppose $x\notin M$ and there is no mine greater than $x$ . If $M$ is empty, we are done; otherwise let $m=\max M$ . Apply induction to the shorter lengths and $M\setminus\{m\}$ . If the resulting path never lands on $m$ , append $a_n$ . If its $k$ th jump $a_k$ lands on $m$ , replace that jump by $a_n$ and put $a_k$ last. The new point at that stage is $m-a_k+a_n>m$ , and every later point is also greater than $m$ ; the final point is $s$ . The same argument handles $x\in M$ with no mine greater than $x$ , by taking $m=x$ and applying induction to $M\setminus\{x\}$ .