Ringing of the Bills: Answer Key

I didn’t get as many answers submitted for this puzzle as I did for the three-sided coin, which I take to mean the puzzle is less interesting. Of the respondents, everyone came up with correct answers for parts (a)-(d) when the ATM dispenses fifties and twenties. Some respondents didn’t respond to the next part, which was to repeat (a)-(d) assuming the ATM dispenses only twenties, but those who did respond got the answers right. Most people only reported taking a few minutes of thinking time.

But I didn’t actually expect people to have difficulty with (a)-(d). The difficult part of the problem was to “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.” About four respondents came up with an accurate statement of the principle. Those who got it reported taking about half an hour to do so.

Here are my answers for (a)-(d), though many answers are possible:

(a) To get five ones instead of one five: Start with two twenties, use one twenty make a $16 purchase, then another twenty to make a $19 purchase.

(b) To get two fives instead of one ten: Start with two twenties, and make two purchases of $15 each using a twenty each time.

(c) To get four fives instead of one twenty: Start with four fifties, and make four purchases of $45 each using a fifty each time. Impossible if the ATM dispenses only twenties.

(d) To get two tens instead of a twenty: Start with two fifties, and make two purchases of $40 each using a fifty each time. Impossible if the ATM dispenses only twenties.

So what about the general principle? Here’s the rule I had in mind: If you want to get n bills of denomination x, and the highest denomination bill available is y, then the task is possible if and only if y > nx. The strict inequality matters: if y = nx, the task is impossible.

In English, Mike Glover stated the principle elegantly: “I can always get one fewer target bill than would make up the maximum available denomination.” Don Lloyd put it even more simply: “The larger bill must not be the largest bill.” (By “larger bill,” he means the bill you’re not supposed to have, e.g., a five in part (a). By “largest bill,” he means the largest available denomination.)

Here’s the proof. Suppose you want to get n bills of denomination x, and y is the largest available denomination. The key issue is whether you can get the nth x-bill when you already have (n – 1) of them. (If you can get the nth x-bill, it’s trivial to show you can get all the previous x bills.) You need to make one more purchase p using a y bill such that y – p = x, or y = x + p. But unless p > (n – 1)x, you’ll use the x bills you already have to pay. So the relevant condition is

y = x + p > x + (n – 1)x

which simplifies to

y > nx

which is the condition I stated earlier.