Results 1 to 4 of 4

Math Help - A problem from a grade 9 math competition

  1. #1
    Newbie dashed's Avatar
    Joined
    Mar 2009
    From
    Toronto
    Posts
    6

    A problem from a grade 9 math competition

    I don't know whether I posted in the proper forum.

    This is a question from a 2009 grade 9 math competition.

    The question
    Starting with the input (m,n), Machine A gives the output (n,m).
    Starting with the input (m,n), Machine B gives the output (m + 3n, n).
    Starting with the input (m,n), Machine C gives the output (m - 2n, n).
    Natalie starts with a pair (0,1) and inputs it into one of the machines. She takes the output and inputs it into any one of the machines. She continues to take the output that she receives and inputs it into any one of the machines. (For example, starting with (0,1), she could use machines B, B, A, C, B in that order to obtain the output (7,6).) Which of the following pairs is impossible for her to obtain after repeating this process any number of times?

    A. (2009, 1016)
    B. (2009, 1004)
    C. (2009, 1002)
    D. (2009, 1008)
    E. (2009, 1032)

    A friend have found D to be suspicious through methods of brute force.

    I looked at the problem for a while, and I've been unable to find a solution.

    Can someone provide insight as to how to solve this particular problem?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by dashed View Post
    I don't know whether I posted in the proper forum.

    This is a question from a 2009 grade 9 math competition.

    The question
    Starting with the input (m,n), Machine A gives the output (n,m).
    Starting with the input (m,n), Machine B gives the output (m + 3n, n).
    Starting with the input (m,n), Machine C gives the output (m - 2n, n).
    Natalie starts with a pair (0,1) and inputs it into one of the machines. She takes the output and inputs it into any one of the machines. She continues to take the output that she receives and inputs it into any one of the machines. (For example, starting with (0,1), she could use machines B, B, A, C, B in that order to obtain the output (7,6).) Which of the following pairs is impossible for her to obtain after repeating this process any number of times?

    A. (2009, 1016)
    B. (2009, 1004)
    C. (2009, 1002)
    D. (2009, 1008)
    E. (2009, 1032)

    A friend have found D to be suspicious through methods of brute force.

    I looked at the problem for a while, and I've been unable to find a solution.

    Can someone provide insight as to how to solve this particular problem?
    Isn't it a bit unethical to be asking for help on a math competition?

    Thread closed (pm me if I've misunderstood the situation).

    Edit: Thread re-opened following a LivelyChat and a pm.
    Last edited by mr fantastic; March 19th 2009 at 04:21 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member billa's Avatar
    Joined
    Oct 2008
    Posts
    100
    This was difficult and I think that there might be an easier way, but here is what I did...
    It is easy to find the possible sets when each element is under 10, so I tried to transform the large sets into ones with smaller elements by reversing the rules
    This process is straightforward and gives you the right answer quickly enough for a timed competition. I also did a google search and someone mentioned that a certain arrangement of the machines gives a fibbonaci sequence, but I wouldn't have noticed that on the test.

    So the answer is...

    Eventually you find that if (2009, 1008) is a possible set, then so is (7,0). This set is not possible because the only way to get it would be to first get (7,7). It isn't possible to get sets with equal elements (other than (1,1)). If you didn't want to figure out if it was possible to get 7,7 you could alternately find that all the other choices were possible. So it is D. (I think)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by dashed View Post
    I don't know whether I posted in the proper forum.

    This is a question from a 2009 grade 9 math competition.

    The question
    Starting with the input (m,n), Machine A gives the output (n,m).
    Starting with the input (m,n), Machine B gives the output (m + 3n, n).
    Starting with the input (m,n), Machine C gives the output (m - 2n, n).
    Natalie starts with a pair (0,1) and inputs it into one of the machines. She takes the output and inputs it into any one of the machines. She continues to take the output that she receives and inputs it into any one of the machines. (For example, starting with (0,1), she could use machines B, B, A, C, B in that order to obtain the output (7,6).) Which of the following pairs is impossible for her to obtain after repeating this process any number of times?

    A. (2009, 1016)
    B. (2009, 1004)
    C. (2009, 1002)
    D. (2009, 1008)
    E. (2009, 1032)

    A friend have found D to be suspicious through methods of brute force.

    I looked at the problem for a while, and I've been unable to find a solution.

    Can someone provide insight as to how to solve this particular problem?
    Notice that the machines A, B, and C all have inverse operations:

    A^{-1}(m, n) = (n, m)
    B^{-1}(m, n) = (m-3n, n)
    C^{-1}(m,n) = (m+2n, n)

    In case you don't know what I mean by an inverse operation, it's running the machine "in reverse".

    Notice also that if m and n have a common divisor d then so do the coordinates of any of the three inverse operations:
    If m and n are divisible by d, then so are n and m.
    If m and n are divisible by d, then so are m-3n and n.
    If m and n are divisible by d, then so are m+2n and n.

    Now, if there is a chain of A, B, C operations that starts with (0,1) and leads to (x,y), then there is a chain of inverse operations that starts with (x,y) and leads to (0,1).

    (Maybe you see where we are headed now...)

    2009 and 1008 are both divisible by 7. For any chain of inverse operations starting with (2009, 1008), at each step both coordinates must be divisible by 7. But 0 and 1 do not have a common factor of 7. So we cannot start with (2009, 1008), apply a sequence of inverse operations, and arrive at (0,1). Turning the chain around, we can't start with (0,1) and get to (2009, 1008) by applying the machine operations.
    Last edited by awkward; April 4th 2009 at 04:44 PM. Reason: clarification
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A nice problem for fun - Iranian math competition
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: December 7th 2009, 09:06 PM
  2. Word Problem : Grade 6 Math
    Posted in the Algebra Forum
    Replies: 4
    Last Post: October 14th 2009, 05:19 PM
  3. math competition
    Posted in the Math Forum
    Replies: 8
    Last Post: August 14th 2008, 07:45 AM
  4. 7th grade math problem???
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 30th 2008, 02:39 PM
  5. [SOLVED] 4th grade math problem
    Posted in the Algebra Forum
    Replies: 5
    Last Post: October 8th 2007, 07:22 PM

Search Tags


/mathhelpforum @mathhelpforum