Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Each of three machines can read a card on which is written a pair of whole numbers $(m,n)$ and print a new card.

  • Machine $\text{A}$ reads $(m,n)$ and prints $(m-n,n)$.
  • Machine $\text{B}$ reads $(m,n)$ and prints $(m+n,n)$.
  • Machine $\text{C}$ reads $(m,n)$ and prints $(n,m)$.

We are given a card $(19,81)$ in the beginning. Is it possible to obtain card $(a,b)$ using described machines finite many times, if (a) $a=7$, $b=13$; (b) $a=12$, $b=21$?

My attempt to solve this problem goes something like this.

First let's notice that we can never get a pair of even numbers with given pair $(19,81)$. Proof. Let's assume that, using these machines, we've gotten a pair of even numbers for the first time. In order to obtain the pair of even numbers, we must have had a pair of even numbers before. Since we are given two odd numbers, we can never get to pair of even numbers.

Now, we notice that using machines A or B, we change the parity of one number: $$ (o,o)\xrightarrow{A/B}(e,o)\quad\text{or}\quad(e,o)\xrightarrow{A/B}(o,o)\quad\text{or}\quad(o,e)\xrightarrow{A/B}(o,e). $$

We notice that having $AB$ (using machine A, then using machine B), $BA$ or $CC$ in sequence is pointless. So after each sequence of $A$'s or $B$'s has to end with $C$, after which we must place sequence of $A$'s or $B$'s again.

Also I tried experimenting by figuring out rules for modulo (for $7$, $13$, etc) but I couldn't figure it out either.

Also please note I'm looking for proof, not for the actual sequence of using machines. I don't have solution. Thanks.

share|improve this question
2  
Hint: Look at gcd of the two numbers, how it changes (or doesn't). (Maybe you can try checking whether each of the 3 operations is reversible.) –  ShreevatsaR Feb 7 '13 at 12:37
    
I guess the pairs available, starting out from $(a,b)$ are the numbers of form $xa+yb$ for $x,y\in\Bbb Z$, and by Bezout's identity, these are just the multiples of $\gcd(a,b)$ –  Berci Feb 7 '13 at 12:47

2 Answers 2

up vote 3 down vote accepted

Note that machine C is its self-inverse, an A and B are the inverse of each other, so we may start from (a) and (b) and try and get to $(19, 81)$.

In case (b), 12 and 21 are both divisible by 3, and this will hold for all pairs derived from them, so you can't get $(19, 81)$..

In case (a), note that using (a) and (c) you can run the Euclidean algorithm on $(7, 13)$ and get $(1, 0)$. Now using (b) and (c) you can run the Euclidean algorithm for $(81, 19)$ backwards and get $$ (1, 0)\ \textit{use (c) to get}\ (0,1)\ \textit{use (b) 4 times to get}\ (4,1)\ \textit{use (c) to get}\ (1,4)\ \textit{use (b) to get}\ (5, 4) \dots (81, 19) $$

share|improve this answer

I assume you are just learning about Euclid's algorithm, so I'll avoid referring to that. I'll just give some hints.

  • Machines A and B are each others inverses, and C is its own inverse. Therefore if one can transform card X into Y, and can also transform Y into X
  • Therefore if we can transform both X and Y into the same card Z, we can transform X and Y into each other.
  • Show that you can always make a card of the form $(0,k)$. This is a good candidate for the target card Z.
  • To show that two cards can never be transformed into each other, you need to find a property of the cards that none of the machines can change, and that distinguishes the two cards. Both numbers being even would be such a property, but you may need something more general.
  • Using such a property, you may be abke to prove the card $(0,k)$ above is unique for any given initial card. You can then decide whether two cards are inter-convertible by transforming both into such a card.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.