Money PuzzleDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/