Money Puzzle

Date: 01/14/98 at 08:37:29
From: Vedachal
Subject: Puzzle

Hi Dr. Math, 

Can you help me out with this puzzle?

A man goes to the bank and asks for x dollars and y cents. The
banker by mistake gives him y dollars and x cents. After spending
5 cents the man realises that he now has twice the amount he asked
for.  What was the amount he asked for?
	
Regards,
Veda

Date: 01/14/98 at 09:56:58
From: Doctor Rob
Subject: Re: Puzzle

Thanks for writing, Veda.

The amount he asked for was 100*x + y cents. The amount he received 
was 100*y + x cents. After spending five cents, he was left with
100*y + x - 5 cents.  Then

   100*y + x - 5 = 2*(100*x + y),
    98*y - 199*x = 5.

You want to find a solution to this equation for which both x and y 
are nonnegative integers, since the problem implies that that must be 
so. The problem also implies that x < 100 and y < 100.

Equations requiring integer solutions are called Diophantine 
equations. This one is first-degree in x and y, so it is a linear 
Diophantine equation. The following technique works.

We want to reduce the size of the coefficients of the unknowns 
x and y. We start by replacing the larger one as follows.  
Since 199 = 2*98 + 3, we can rewrite the equation as

   98*y - (2*98 + 3)*x = 5
    98*(y - 2*x) - 3*x = 5

Put z = y - 2*x, which will still be an integer.  Then y = z + 2*x.
Then

            98*z - 3*x = 5

Now since 98 = 32*3 + 2, we can rewrite this equation as

    (32*3 + 2)*z - 3*x = 5
    2*z - 3*(x - 32*z) = 5

Put w = x - 32*z, which will still be an integer.  Then x = w + 32*z.
Then

             2*z - 3*w = 5

Now since 3 = 1*2 + 1, we can rewrite this equation as

     2*z - (1*2 + 1)*w = 5
         2*(z - w) - w = 5

Put v = z - w, which will still be an integer.  Then z = v + w.  Then

               2*v - w = 5
                     w = 2*v - 5

Now if v is any integer, we can work backwards to figure out all the
other variables in terms of v.  We have

   w = 2*v - 5
   z = v + w = v + (2*v - 5) = 3*v - 5
   x = w + 32*z = (2*v - 5) + 32*(3*v - 5) = 98*v - 165
   y = z + 2*x = (3*v - 5) + 2*(98*v - 165) = 199*v - 335

These last two equations give all solutions to the equation we started
with, 98*y - 199*x = 5. We still must use the conditions on x and y.
Now in order that

            100 > x >= 0
   100 > 98*v - 165 >= 0
         265 > 98*v >= 165
         265/98 > v >= 165/98

Similarly,

            100 > y >= 0
  100 > 199*v - 335 >= 0
        435 > 199*v >= 335
        435/199 > v >= 335/199

You can figure out what the only possible integer value of v is, and
that will tell you what x and y are, once you know v.

Be sure to check your answer!

Similar problems can be handled in the same kind of way, by reducing 
the coefficients of the unknowns (y, x, z, w, v in this case, reduced 
via 198, 99, 3, 2, and 1) until one of them divides the other evenly 
(in this case, 1 divides 2 evenly), then working backwards.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/