Take the 2-minute tour ×

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
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
add comment

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
add comment

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
add comment

Your Answer


