Wikipedia
Search Wikipedia:

Latest topics
» Role of Alcohol in general chemistry
Fri Dec 15, 2017 12:17 am by bejoy

» Dendrimers for drug delivery
Mon Dec 11, 2017 1:23 am by bejoy

» Catalysis and its importance in chemical industry
Thu Nov 09, 2017 5:06 am by bejoy

» Cracking: Breaking up larger molecules
Thu Nov 09, 2017 5:05 am by bejoy

» What is Alkylation?
Fri Nov 03, 2017 12:35 am by bejoy

» An Ultimate Guide on Diamond
Thu Nov 02, 2017 2:15 am by bejoy

» Chemistry Running Behind Anger
Mon Oct 30, 2017 12:31 am by bejoy

» The Discovery of Four New Elements in the Periodic Table
Wed Oct 25, 2017 1:23 am by bejoy

» Carbonic Acid: Occurrence, Preparation, Properties and Uses
Mon Oct 23, 2017 1:39 am by bejoy

December 2017
MonTueWedThuFriSatSun
    123
45678910
11121314151617
18192021222324
25262728293031

Calendar Calendar

Free Hit Counter

Pascal Contest, 2009, question 25

View previous topic View next topic Go down

Pascal Contest, 2009, question 25

Post  karooomph on Wed Feb 18, 2009 10:46 pm

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)


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?)
avatar
karooomph

Posts : 74
Join date : 2008-11-19
Age : 23
Location : ubseikastan

View user profile

Back to top Go down

Re: Pascal Contest, 2009, question 25

Post  bfrsoccer on Thu Feb 19, 2009 8:32 pm

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.
avatar
bfrsoccer
Administrator

Posts : 61
Join date : 2008-11-09

View user profile

Back to top Go down

Re: Pascal Contest, 2009, question 25

Post  karooomph on Fri Feb 20, 2009 7:54 pm

thank you.

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

Posts : 74
Join date : 2008-11-19
Age : 23
Location : ubseikastan

View user profile

Back to top Go down

Re: Pascal Contest, 2009, question 25

Post  bfrsoccer on Sat Feb 21, 2009 2:21 am

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.
avatar
bfrsoccer
Administrator

Posts : 61
Join date : 2008-11-09

View user profile

Back to top Go down

Re: Pascal Contest, 2009, question 25

Post  karooomph on Sat Feb 21, 2009 10:16 pm

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?
avatar
karooomph

Posts : 74
Join date : 2008-11-19
Age : 23
Location : ubseikastan

View user profile

Back to top Go down

Re: Pascal Contest, 2009, question 25

Post  bfrsoccer on Sat Feb 21, 2009 11:07 pm

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
avatar
bfrsoccer
Administrator

Posts : 61
Join date : 2008-11-09

View user profile

Back to top Go down

Term Papers

Post  monti on Wed Apr 28, 2010 6:39 am

Keep up this good work of helping others. Two thumbs for you.

Term Papers

monti

Posts : 10
Join date : 2010-04-28

View user profile

Back to top Go down

got the answer

Post  paullin on Thu May 06, 2010 5:23 am

Thank you, I got it.

paullin

Posts : 1
Join date : 2010-05-06

View user profile

Back to top Go down

Re: Pascal Contest, 2009, question 25

Post  Sponsored content


Sponsored content


Back to top Go down

View previous topic View next topic Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum