Results 1 to 7 of 7

Math Help - Grasshopper

  1. #1
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301

    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 .
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Sampras View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    Quote Originally Posted by NonCommAlg View Post
    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 .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Sampras View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    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 .
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    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.)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    Quote Originally Posted by Opalg View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum