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 1 of 5: Strengthen the induction statement and set the notation

Previous step Next step

In plain words

The longest jump is the natural final jump. The point just before it is the key checkpoint.

a_1<\cdots<a_n,\quad s=a_1+\cdots+a_n,\quad x=s-a_n

Detailed analysis

We prove the slightly stronger statement by induction on $n$ : for any set of at most $n-1$ positive forbidden points whose total $s$ is not forbidden, the jumps can be ordered safely. Arrange the lengths as $a_1<\cdots<a_n$ , write $s=a_1+\cdots+a_n$ , and put $x=s-a_n$ . The case $n=1$ is immediate.