Hard Imo Question

Question

Let $a_1,a_2,…,a_n$ be distinct positive integers and let $M$ be a set of $n−1$ positive integers not containing $s=a_1+a_2+…+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,…,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$.

It's pretty intuitive, and I've tried proving it by induction but to no avail. Can someone please give me a hint (or post the answer if they'd like, I don't mind)?

Answer 1

This is worth thinking about yourself until you drive yourself mad - that's how I learned to solve such things. It was found difficult in the original Olympiad when it was set, but involves nothing really complicated.

For a hint:

First try putting the longest leap at the right-hand end. If you can jump an element of $M$ without landing on an element of $M$ you have an induction. If you haven't managed to jump an element of $M$ take out the right-hand element of $M$ and the longest leap. How far can you now get starting at the left? Put the right-hand element of $M$ back in and use the longest leap to avoid it ... fill in the details.