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 4 of 5: Find a safe pair in the difficult case

Previous step Next step

In plain words

The mine at the checkpoint cannot block either member of a pair, and every other mine can block at most one pair.

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

Detailed analysis

Now suppose $x\in M$ and $M\cap(x,\infty)\ne\varnothing$ . Let $m=\max M$ . For each $i$ with $1\le i\le n-1$ , define $u_i=s-a_i$ and $v_i=s-a_i-a_n=x-a_i$ . Then $v_i<x<u_i$ , so the mine $x$ blocks none of these $n-1$ pairs. The $u_i$ are distinct and all lie above $x$ , while the $v_i$ are distinct and all lie below $x$ ; hence each of the other $n-2$ mines can block at most one pair. Therefore, among the $n-1$ pairs, some index $i$ has $u_i\notin M$ and $v_i\notin M$ .