# Problem 1: The piggy bank

We call this first problem The Piggy Bank. It has most of the features that we are looking for in a good problem, and it avoids most of the pitfalls of trivia quizzes.

We present this problem first because of several features:

1. It is not terribly complicated. No special math skills beyond the minor arithmetic that we do every day when we go shopping.
2. It is a good one for interviewers to study, and a good one to inspire the creation of your own questions. As an interviewer, work it out for yourself before you interview a candidate.
3. It is easy to tell the candidate what their answers reveal without prejudicing the solution process.
4. It has been around for a long time — we did not invent it here.

### Preamble

My wife says that there is only one thing that I do that is a major annoyance: I leave little piles of coins on nightstands, on coffee tables, on the kitchen counter. It seems that my pockets are self-emptying – the coins go directly from the retailer, to me, and then to our furniture. I count myself lucky that there is only one thing I do that upsets the domestic tranquility.

In the interests of peace, I periodically have a “coin amnesty” during which I gather up all the stray pennies, nickels, dimes, and quarters and put them in a metal tin in which tea arrives. When the tin is full, I take the coins to the bank and exchange the collection for larger denominations of currency.

I have now been doing this about twice a year for the past seven years. I have noticed that the tin is, ±10%, worth the same amount of money. It is not a terribly surprising finding when you consider that coins are obtained in the same way, from the same sources, over a reasonable period of time.

### Essential questions

Suppose I present you with a box that contains exactly 1,000 coins gathered in the above way – somewhat randomly from circulation.

1. How much would you pay for the box of 1,000 coins? (or perhaps how much is it worth?)
2. What are some different ways you can go about determining the answer?

### Analysis questions

Now, let’s make this problem more interesting by adding features that require analysis:

1. Before 1968 (in the United States), the \$0.50 coin, known as the “half dollar,” used to circulate freely. Assume that the half dollar has made a comeback. What is effect of such a coin’s circulation on the value of 1000 coins?
2. Australia uses a \$0.20 coin instead of a \$0.25 coin. Is this a better choice? What are the criteria for “better?” Ignoring the exchange rate, would you pay more or less for 1,000 coins using the 20? (Note that Australia uses the half dollar.)

### Bonus questions

Some people are going to be really engaged, and for them it is wise that we have a bonus round.

[A] Let’s wander out into fantasy: Suppose that you could introduce a coin not previously discussed that could have any value, even negative. For example,

1. if you had a coin worth \$0.07 you could make \$0.17 in change by using a dime and this coin.
2. if you had a coin worth -\$0.05, then you could make \$0.45 in change by providing a half dollar and this coin.

Does any such coin work to increase the net value of 1,000 coins? Why? How?

[B] Is there an easily defined set of coins that allow all change to be made with a minimum number of coins? (I.e., we don’t want to arrive at the answer by testing every imaginable combo of coins …)

### This problem is about …

This problem primarily examines the candidate’s ability to explain the proposed solution to the examiner. The problem can be made arbitrarily difficult depending on how many assumptions you want to make about the coins, and how finely detailed one’s analysis becomes during the course of the exam.

There is something here for everyone: People who perseverate on extremely fine points such as “Which amounts of coin change are the most commonly encountered?” make poor ex nihilo problem solvers regardless of their programming abilities. On the other hand, they make good optimizers.

It is also a good way to spot distracted thinking: For example, less experienced thinkers may opine about the size or weight of the coins. This is irrelevant since the only thing that matters is that there are 1,000 coins, not the size of the jar that contains them.

The solution process

Candidates are off to a good start if they say something along the lines of “I guess it has to be at least worth \$10.00 if it is all pennies, and at most it is worth \$250.00 if it is all quarters.” If at this point they immediately say, “It’s probably worth about \$125.00,” we are off to a really good start in the sense that it is a reasonable hypothesis that the correct answers are likely to be nearer the center of the range than the extremes.

Good candidates will divine that this is a finite analysis type of problem. There are only 99 possibilities for the value of the coins you can receive in change (assuming you get any at all): {1, 2, 3, …, 99}. Most cashiers or mechanical change makers will give you coins starting with the largest denominations, and move to smaller ones as needed. Assuming that each of these has an equal chance of occurrence then it is a matter of addition to figure out the ratios based on 100 possible outcomes.

If people work this out for themselves and give a satisfactory explanation, then it is time to move on to the more interesting questions involving the 20 cent and 50 cent coins. Each one offers the candidate a chance to see that the new issues in the problem allow one to reduce the problem to the previous one. The 50 cent coins swap out for for two 25 cent coins. The 20 cent coin is more complicated: it can be used any time there are two 10 cent coins but replaces the 25 cent coin.

The final two questions (which new coin, and the optimal set) require a bit more thinking. I would be interested in people who approach the problem with an idea like “I think a 2 cent coin would be good,” and then can give a reason for thinking this.

Let’s leave the optimum set unanswered.