# Pascal Contest, 2009, question 25

## Pascal Contest, 2009, question 25

Starting with the input

Starting with the input

Starting with the input

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?

*(m,n)*, Machine A gives the output*(n, m)*.Starting with the input

*(m,n)*, Machine B gives the output*(m +*3*n, n)*.Starting with the input

*(m,n)*, Machine C gives the output*(m -*2*n, 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)Last edited by karooomph on Wed Feb 18, 2009 10:49 pm; edited 1 time in total (Reason for editing : why can't you tab anything?)

**karooomph**- Posts : 74

Join date : 2008-11-19

Age : 23

Location : ubseikastan

## Re: Pascal Contest, 2009, question 25

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.

**bfrsoccer**- Administrator
- Posts : 61

Join date : 2008-11-09

## Re: Pascal Contest, 2009, question 25

thank you.

oh, btw, of what my friends have told me, the answer is

oh, btw, of what my friends have told me, the answer is

**D**, if that helps.**karooomph**- Posts : 74

Join date : 2008-11-19

Age : 23

Location : ubseikastan

## Re: Pascal Contest, 2009, question 25

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.

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**- Administrator
- Posts : 61

Join date : 2008-11-09

## Re: Pascal Contest, 2009, question 25

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*. ?

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

*EDIT***karooomph**- Posts : 74

Join date : 2008-11-19

Age : 23

Location : ubseikastan

## Re: Pascal Contest, 2009, question 25

Yeahkarooomph 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?

**bfrsoccer**- Administrator
- Posts : 61

Join date : 2008-11-09

Similar topics

» Question on Lambda symbol for light

» Amendments to the Revised IRR through GPPB Resolution No. 06-2009

» UPDATED[MediaFire]3 Idiots • 2009 • 550MB • X264 DVDRiP • English SubTitles •

» Migraine contest winners...

» Eurovision Song Contest 2012

» Amendments to the Revised IRR through GPPB Resolution No. 06-2009

» UPDATED[MediaFire]3 Idiots • 2009 • 550MB • X264 DVDRiP • English SubTitles •

» Migraine contest winners...

» Eurovision Song Contest 2012

Page

**1**of**1****Permissions in this forum:**

**cannot**reply to topics in this forum