# Math Help - Grasshopper

1. ## Grasshopper

A grasshopper starts at $0$ is to jump right $(a_1, \dots, a_n)$ in any order where each $a_i >0$ and are integers. Let $M$ be a set of $n-1$ numbers not containing $s = a_1 + \cdots + a_n$. Prove that the order can be chosen in such a way so that the grasshopper never lands on any point in $M$.

2. Originally Posted by Sampras
A grasshopper starts at $0$ is to jump right $(a_1, \dots, a_n)$ in any order where each $a_i >0$ and are integers. Let $M$ be a set of $n-1$ numbers not containing $s = a_1 + \cdots + a_n$. Prove that the order can be chosen in such a way so that the grasshopper never lands on any point in $M$.
is it only me in here who read this question a few times and still didn't understand it?

3. Originally Posted by NonCommAlg
is it only me in here who read this question a few times and still didn't understand it?
Let $a_1, \dots, 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 $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$.

4. Originally Posted by Sampras
Let $a_1, \dots, 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 $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$.
this explanation didn't help! there's something important missing in your question: if M is just a set, why would basically the "order" of $a_j$ have any significance?

for example, the grasshopper will eventually land on, say $a_1.$ so what if M contains $a_1$?

5. An integer $p$ can be reached by the grasshopper in $k$ moves if there exist distinct $b_1, \dots, b_k \in \{a_1, \dots, a_n \}$ such that $p = b_1 + \cdots + b_k$ and none of the partial sums $b_1 + \cdots + b_i$ for $1 \leq i \leq k$ is in $M$.

6. Before spending too much time pondering this puzzle, you might like to know that it was the "hard" problem in this year's math olympiad, and has been the object of a massive cooperative solving venture on Terence Tao's blog. (I haven't been following this project carefully, but I believe that it hasn't yet reached a solution, though Prof. Tao claims to have found a solution after seven hours' thought, and it seems that three of the olympiad competitors scored full marks on the question.)

7. Originally Posted by Opalg
Before spending too much time pondering this puzzle, you might like to know that it was the "hard" problem in this year's math olympiad, and has been the object of a massive cooperative solving venture on Terence Tao's blog. (I haven't been following this project carefully, but I believe that it hasn't yet reached a solution, though Prof. Tao claims to have found a solution after seven hours' thought, and it seems that three of the olympiad competitors scored full marks on the question.)
He solved it after 7 hours of doing other stuff (e.g. he was on a plane for most of that time I think). There are solutions already posted on the wiki. But I wanted to see if people could come up with their own proofs.