I have a riddle that I’ve been asked, and I can’t it out. Here it is
A man writes a check for x dollars and y cents. He then hands it to the dyslexic teller who gives him y dollars and x cents back. He then goes to a gas station, purchases an item for 3.50. He looks at whats left and sees that it is exactly double the amount that he wrote on the check ( x dollars and y cents)
How much was the original check?
If anyone knows Visual Basic, could I solve this with some sort of loop?
Incidentally, the problem leads to a Diophantine equation with two unknown variables. Ordinary algebra leads you part of the way, but doesn’t solve it. I basically used brute force in an Excel spreadsheet: 99 rows, with every possibe value of one variable, together with a formula saying what the other variable must be, and choosing the one which had an integer value. However, there are more sophisticated ways of solving these equations.
Actually, I think the answer that **Giles[/] gives in post #3 is the amount the cashier wrongly gave him in the first step, not the amount on the check, which I’m pretty sure would have been $14.32.
To answer the OP, it can be solved by a really simple Visual Basic program: just set a loop counter to step x from 0 to 99, and check for integer solutions less than 100 (same as the Excel method, but slightly less code to write).
I think it’s already been shown that x,y must satisfy -199x + 98y = 350. Since x,y are integers, this is a linear Diophantine equation.
First, we need to find the greatest common divisor (GCD) of the coefficients of x and y. The GCD of -199 and 98 is 1. In order for our equation to have a solution, this GCD must divide the constant, 350, which of course it does, so we’re in luck.
Next, write the GCD as a linear combination of -199 and 98. It doesn’t matter how you do it, just find a way. It can be done systematically using the Euclidean algorithm, if you like.
Anyway, I got
-33(-199) - 67(98) = 1.
Multiply both sides of this by 350:
-11550(-199) - 23450(98) = 350
So x=-11550, y=-23450 is a solution to our equation. Of course, it obviously doesn’t make any sense as an answer to the original question, so we’ve still got work to do.
Let’s call the above solution x’, y’ (= -11550, -23450, respectively). There are others, and we’re gonna have to find them.
If I change x’ to, say, x’ + a, then y’ is gonna have to change to if we want to keep the equation balanced, call it y’ + b:
-199(x’ + a) + 98(y’ + b) = 350
A little algebra shows:
199a = 98b
Since 199 and 98 are relatively prime, this means 98 divides a, so let’s write a as 98t:
19502t = 98b
Solve for b, and you get
b = 199t.
t, of course, can be any integer.
So our general solution is:
x = -11550 + 98t, y = -23450 + 199t (t any integer).
Both x and y have to be between 0 and 100 for our answer to make any sense. If you look at the equation for y, you’ll see this can only happen for one value of t, t=118. This gives x=14, y=32, so the check was originally written for $14.32.
I realise that we shouldn’t use this forum to compensate for our not listening in high school, but my lifelong antipathy towards mathematics might be ameilorated a little if I were to understand two of the steps in this solution:
What does “linear combination” mean here? Why -33 and -67, rather than any of the other (presumably infintely many) numbers that could be in this equation?
What does “relatively prime” mean, and why does this fact mean that 98 divides a? Could the original problem be solved if this wasn’t the case?
Please feel free to point me at a more appropriate site, if this sort of question is too elementary.
A linear combination of -199 and 98 means “an integer times -199 plus an integer times 98”, i.e., -199x + 98y, where x and y are any integers.
An interesting thing about the GCD of two integers: It is the smallest positive number that can be written as a linear combination of the two integers. That’s how I know -199x + 98y = 1 has a solution with x and y both integers.
To find it, we can use the Euclidean algorithm. The Euclidean algorithm is a method for finding the GCD of two numbers. Here’s how it works for 199 and 98: First divide the smaller into the larger, and get a remainder:
199 = 98 * 2 + 3
Now do the same thing with 98 and 3 (98 was the number we just divided by, 3 was the remainder): Divide 98 by 3:
98 = 3 * 32 + 2
Again, with 3 and 2 (like before, 3 was the number we just divided by this time, and 2 was our remainder):
3 = 2 * 1 + 1
We just divided by 2, and 1 was our remainder, so that’s what I use next: 2 divided by 1:
2 = 1 * 2 + 0
Eventually you’ll get zero as a remainder (like we just did). The last nonzero remainder we had is the GCD of 199 and 98. This was 1, so we just showed 1 is their GCD.
Now work backwards to write 1 as a linear combination of 199 and 98. From the next to last equation:
1 = 3 - 2
From the equation before that:
1 = 3 - (98 - 332) = -98 + 333
And from the equation before that:
1 = -98 + 33*(199 - 982) = 33199 - 67*98
So -199x +98y = 1 has a solution x=-33, y=-67. This particular solution isn’t really special, it just happens to be the one I found. All we need is any linear combination of -199 and 98 which equals 1.
We had 199a = 98b. “Relatively prime” just means their GCD is 1, like we showed above. It means they have no prime factors in common.
98 factors into 277. 199 factors into 199 (it is prime, itself).
The prime factorization of an integer is unique. Since 199a = 98b, there’s got to be a prime factor of 199 in 98b. It obviously isn’t in 98, so it’s gotta be in b (so 199 divides b).
Similarly, 199a must have prime factors 2, 7, and another 7. They obviously ain’t in 199, so they gotta be in a. This means 277 = 98 divides a.
If we had gotten to that stage of the problem and didn’t have relatively prime numbers, we could still go on. For example, if we had instead ended up with:
30a = 12b
30 and 12 obviously aren’t relatively prime. Their GCD is 6. Divide both sides by 6:
Once you’ve done that, from here it’s just like before. 5 and 2 are relatively prime, so we can say, for example, 5 divides b. Write b=5t. Then of course, a=2t.