IMO 2009 · Problem 6

Let \(a_1,a_2,\ldots,a_n\) be distinct positive integers and let \(M\) be a set of \(n-1\) positive integers not containing \(s=a_1+a_2+\cdots+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,\ldots,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\).

Official text of the problem. Official problem paper (PDF)

Solution

We prove the slightly stronger assertion allowing \(M\) to contain at most \(n-1\) positive integers, with \(s\notin M\).

We use strong induction on \(n\). For \(n=1\), the set \(M\) is empty and the assertion is immediate. Now suppose \(n\ge2\) and the assertion holds for every smaller number of jumps. If \(M\) is empty there is nothing to prove, so assume otherwise.

Relabel the lengths so that \[ a_1<a_2<\cdots<a_n, \] and put \[ A=a_n,\qquad t=s-A,\qquad m=\max M. \]

Case 1: \(t\notin M\setminus\{m\}\).

The \(n-1\) lengths \(a_1,\ldots,a_{n-1}\) have total \(t\), and \(M\setminus\{m\}\) contains at most \(n-2\) points. By induction, these lengths can be ordered as \(b_1,\ldots,b_{n-1}\) so that their successive partial sums avoid \(M\setminus\{m\}\).

If these partial sums also avoid \(m\), append the jump \(A\). Its landing point is \(s\notin M\), so this gives the required order.

Otherwise, suppose the jump \(b_k\) lands at \(m\). Insert \(A\) immediately before \(b_k\). All earlier landing points are less than \(m\) and avoid \(M\). The inserted jump lands at \[ m-b_k+A>m, \] because \(A>b_k\). Every subsequent landing point is larger still, hence exceeds every point of \(M\). This order therefore works.

Case 2: \(t\in M\setminus\{m\}\).

Here \(m>t\), and \(M\) contains at least two points, so \(n\ge3\).

For each \(j\in\{1,\ldots,n-1\}\), define \[ u_j=t-a_j,\qquad v_j=s-a_j=u_j+A. \] Since \(A>a_j>0\), we have \[ u_j<t<v_j. \] The numbers \(u_1,\ldots,u_{n-1}\) are distinct, as are \(v_1,\ldots,v_{n-1}\). Thus the \(n-1\) pairs \[ \{u_j,v_j\}\qquad (1\le j\le n-1) \] are pairwise disjoint, and none contains \(t\).

But \(M\setminus\{t\}\) has at most \(n-2\) elements. Consequently, at least one of these pairs is disjoint from \(M\). Fix its index \(j\), so that \[ u_j\notin M,\qquad v_j\notin M. \]

Remove the two lengths \(A\) and \(a_j\). The remaining \(n-2\) lengths have total \(u_j>0\). Let \[ M'=\{x\in M:x<u_j\}. \] Both \(t\) and \(m\) exceed \(u_j\), so \[ |M'|\le |M|-2\le n-3. \] By induction, the remaining lengths can be ordered so that all their landing points avoid \(M'\). These points are at most \(u_j\); since \(u_j\notin M\), they therefore avoid all of \(M\).

Finally, append the jumps \(A\) and \(a_j\), in that order. Their landing points are \[ u_j+A=v_j\notin M \quad\text{and}\quad v_j+a_j=s\notin M. \] This completes the induction and proves the assertion. \(\square\)

The solution was checked against the official IMO shortlist solutions.