, 2009

(By Anton Mellit, observer from the Ukraine delegation, and Ilya Bogdanov, observer from the Russia delegation).

We will represent a route of the grasshopper by a (ordered) sequence of indices $(i_1, i_2, \dots, i_n)$ if it makes consecutive jumps $(a_{i_1}, a_{i_2}, \dots, a_{i_n})$.

To simplify our argument a bit, we prove the following statement:
Let $a_1, a_2, \dots, a_n$ be distinct positive integers and let $M$ be a set of no more than $n-1$ integers not containing $s = a_1 + a_2 + \dots + a_n$. A grasshopper is to jump along the real axis, starting at the point $0$ and making $n$ jumps to the right with lengths $a_1, a_2, \dots, a_n$ in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in $M$.

We induct on $n$. The base case $n=1$ is rather trivial. For the inductive step, we assume that the claim is true for all values $n$ smaller than some integer $k > 1$. We now consider $n=k$. Without loss of generality, we may assume that $a_1 < a_2 < \dots < a_k$. Let $M = \{r_1, r_2, \dots, r_{k-1}\}$, with $r_1 < r_2 < \dots < r_{k-1}$. We divide into several cases.

(a1) In this case, we assume that $r_1 < a_n$ and $a_n \notin M$. Then we apply the induction hypothesis to $M_1 = M \setminus \{r_1\} - a_n = \{r_2 - a_n, r_3 - a_n, \dots, r_{n-1} - a_n\}$ using jumps $a_1, a_2, \dots, a_{n-1}$. Putting $a_n$ at the beginning of this sequence of jumps provides the desired route.

(a2) In this case, we assume that $r_1 < a_n$ and $a_n \in M$. Consider the $n$ pairwise disjoint sets
$$\{a_n\}, \{a_1, a_1 + a_n\}, \{a_2, a_2 + a_n\}, \dots, \{a_{n-1}, a_{n-1} + a_n\}.$$
Because $M$ only has $n-1$ elements, there is an index $i$ such that $\{a_i, a_i + a_n\}$ is disjoint from $M$. It follows that there are at most $n-3$ elements in the intersection of $M$ and the interval $[a_i + a_n, s]$, because $r_1$ and $a_n$ are not in the interval. We apply the induction hypothesis to $M_2 = M \cap [a_i + a_n, s] - (a_i + a_n)$ using jumps $a_1, a_2, \dots, a_{i-1}, a_{i+1}, \dots, a_{n-1}$. Putting $a_i$ and $a_n$ at the beginning (in that order) provides the desired route.

(b) In this case, we assume that $r_1 \ge a_n$. We consider $M_3 = M \setminus \{r_1\} - a_n = \{r_2 - a_n, r_3 - a_n, \dots, r_{n-1} - a_n\}$. We apply the induction hypothesis to $M_3$ using jumps $a_1, a_2, \dots, a_{n-1}$; and let the resulting route be $\mathcal{R}_{n-1} = (i_1, i_2, \dots, i_{n-1})$.

If this route $\mathcal{R}_{n-1}$ does not step on $r_1 - a_n$ (in particular, it follows that $r_1 > a_n$), then the route $\mathcal{R}_n = (a_n, i_1, i_2, \dots, i_{n-1})$ will do the job.

Otherwise, the route $\mathcal{R}_n$ contains exactly one point of $M$, namely, $r_1$. Hence, there exists an index $k$ with $1 \le k \le n-1$ such that
$$a_n + a_{i_1} + \dots + a_{i_k} = r_1.$$
We then consider the route
$$\mathcal{R}'_n = (i_1, i_2, \dots, i_{k+1}, a_n, i_{k+2}, \dots, i_{n-1}).$$
We claim that this route $\mathcal{R}'_n$ will do the job, which completes our proof. Indeed, because
$$a_{i_1} + \dots + a_{i_{k+1}} < a_{i_1} + \dots + a_{i_k} + a_n = r_1,$$
the grasshopper will not land on the points of $M$ during the first $k+1$ jumps. On the other hand, during the remaining part of the route, it lands on the same points as in the route $\mathcal{R}_n$ (and these points are not less than $a_{i_1} + a_{i_2} + \dots + a_{i_{k+1}} + a_n > r_1$), so it will not land on points of $M$ as well. Therefore, this route $\mathcal{R}'_n$ allows the grasshopper to completely avoid landing on points in $M$.