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 5 of 5: Finish with the safe two-jump tail

Previous step Next step

In plain words

Use induction to reach the point before the two selected jumps, then those jumps land at the two safe checkpoints and finally at the safe total.

(b_1,\ldots,b_{n-2},a_n,a_i)

Detailed analysis

For the index $i$ found above, apply induction to the $n-2$ lengths other than $a_i$ and $a_n$ , with forbidden set $M\setminus\{x,m\}$ . Its total is $v_i$ , which is not forbidden, so let their safe order be $(b_1,\ldots,b_{n-2})$ . Use the order $(b_1,\ldots,b_{n-2},a_n,a_i)$ . The first part avoids the remaining mines; the next landing is $v_i+a_n=u_i$ , the last landing is $u_i+a_i=s$ , and both are safe. This completes the induction.