Pascal Contest, 2009, question 25

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 the 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 input (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)

I'm not sure how to do it right now, and I have to get back to studying for my physics and Spanish tests and doing my homework, but I'll take another look at it tomorrow.

thank you.

oh, btw, of what my friends have told me, the answer is D, if that helps.

I think I got it.

I couldn't come up with a particularly nice clever solution, so I started with (0,1) and started to symbolically see what happens when the different machines are applied. So, I basically have (with each letter representing the machine applied):

(note that starting with machine A and then using the other ones doesn't do anything)

(0,1) -> B or C -> (#,1) -> A -> B or C -> (1+x*#,#) -> ... ->x*#+1,y*(a*#+1)

Applying machines B and C produces a multiple of the current n number

Anyway, with all of this multiplication and numbers being multiples of another (trying to test things such as whether 2009-3*n=n didn't help), I decided to start finding the greatest common denominator (gcd) for each group, and noticed a nice pattern. The gcd for each pair was 1, except for (2009,1008), which is 7. And after looking back at my previous work and the problem, the gcd has to be 1 because you're starting with (0,1), which has a gcd of 1, and, also, looking at the pattern above, one number will always have the +1 at the end throwing it off.

bfrsoccer wrote: also, looking at the pattern above, one number will always have the +1 at the end throwing it off.

nice solution and thanks a ton, but what do you mean by one number will always have the +1 at the end throwing it off. ?

EDIT - oh, nvm, are you're saying the +1 at the end will cause the numbers not to have a GCF greater than 1, right?

karooomph wrote:oh, nvm, are you're saying the +1 at the end will cause the numbers not to have a GCF greater than 1, right?

Yeah