Tuesday, April 18, 2006

The Ringing of the Bills

[There was an error in the original version of this post. I think I've successfully corrected it now.]

It’s easier to solve a puzzle than to design one. Still, I had moderate success once before, so I’m trying again. I think this one’s pretty low on the difficulty scale, but still interesting. DON’T POST ANSWERS IN THE COMMENTS SECTION! Please email your answers to me (at the address in the left-hand column), and tell me approximately how long it took you.

Suppose you make one visit to an ATM machine, which dispenses only twenties and fifties. Suppose that money only leaves your wallet when you make purchases, and after your ATM withdrawal it only gets into your wallet as change from purchases. When you make a purchase, you always give the cashier the minimum amount of money possible given what's in your wallet (for example, if you were making a \$7 purchase, you’d never hand over a ten if you had a five and two ones in your wallet). When cashiers give you change, they always give correct change, and they always do so using the minimum number of bills possible (for example, if you were owed \$15, the cashier would give you a ten and a five, not three fives); assume cash registers always have the bills necessary to follow this rule. Given these rules, does there exist a sequence of events that would lead you to look in your wallet and find...

(a) ... five ones instead of one five?
(b) ... two fives instead of one ten?
(c) ... four fives instead of a twenty?
(d) ... two tens instead of a twenty?

Answer (a)-(d) again assuming the ATM only dispenses twenties. Can you state a general principle for when it’s possible to end up with a number of smaller bills instead of a larger bill (or bills) with the same sum?

UPDATE: I've posted the answers here.