A problem from a grade 9 math competition

Printable View

March 19th 2009, 01:57 AM
dashed

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?
March 19th 2009, 03:23 AM
mr fantastic

Quote:

Originally Posted by dashed

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.
April 2nd 2009, 11:40 AM
billa

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)
April 4th 2009, 04:38 PM
awkward

Quote:

Originally Posted by dashed

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.