This is a question from a math competition. The question Starting with the input

Question

This is a question from a 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 themachines. She takes the output and inputs it into any one of themachines. She continues to take the output that she receives andinputs 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 obtainthe output (7,6).) Which of the following pairs is impossible forher 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)

My friends have figured the answer is D by solving it manually(brute force). I'd like to find a solution in which to solve thisquestion algebraically.

I've had some progress but I am stuck. I know that for the case of(0,1), Machine A of any repetitions cannot be the secondstep.

Starting with (m, n), any steps of Machine B and/or C it wouldbe:

(m + n[3b -2c], n)

where b and c are the number of steps.

If someone can provide the solution, I'd love to see it. :)

Explanation / Answer

unfortunatly setting up an equation for this system of randomevents would be an amazing feat, though i'm sure someone can andhas done it. The way i did it was a more simplistic way but stillrequired some number crunching. taking all the possible values A-E, I perfomed the threepossible opporations on them in order to find the combination thatcame before it. I'm omitting the first opporation due totheir trivial outcomes.             (m+3n,n)       (m-2n,n) A     (-1039,1016)   (4041,1016) B     (-1003,1004)   (4017,1004) C     (-997,1002)     (4013,1002) D     (-1015,1008)   (4015,1008) E     (-1087,1032)    (4073,1032) Comparing these values to one another you'll see twothings    1) the first value of each pair is alwaysodd, and the second is always even. (kinda cool)    2) set D is the only pair divisable by5. Because of this i believe D is the answer. sorry for not having a systematic formula. I would also liketo see one.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.