Solution To Yesterday’s Puzzle

The results are in from yesterday’s coinage puzzle! It’s great to know that I have such intelligent (ahem, nerdy) readers. And for so many people to be interested in the solution (ahem, nerd wannabes)! May God bless you with Trekkie husbands.

Steve’s Idea To Optimize Returns (Greedy Approach)

Steve’s comment in the previous post introduced the ingenious idea of utilizing change to maximize returns in quarters. That’s a brilliant way to convert your skimpy, inferior coinage into the vastly superior, beloved, useful quarter. But to draw from this idea, we must consider that quarters are not only desirable because of their utility, but because they are the largest denomination (in this puzzle), so whatever technique gains the most quarters will also be the optimal in terms of fewest coins! But what we must be wary of the idealism of Steve’s approach is that even though you maximize quarters, you still have in your pocket some of the original 7 coins you brought with you. The idea of a greedy algorithm started us off in the right direction, but Shinn brought it home with his lazy algorithm.

Shinn’s Idea To Simplify Transactions (Lazy Approach)

Shinn, who allegedly spent most of his day looking at the problem because he was stranded in Pomona and couldn’t come to ROCK, came to a great realization: that actually my whole theory about making “intelligent” change and Steve’s idea to maximize quarter returns are both entirely moot! Regardless of what amount of change you have in your pocket, if you simply pay with all of it, then the difference you receive back will be in an optimal arrangement of that amount. Basically, you’re letting the cashier collect all of the change in your pocket (even if you have 20 pennies), and return it back optimally (he would give back two dimes). Fantastic! No thinking involved! The cashier becomes your consistent and reliable “black box” change optimizer.

The Solution: Putting It Together

Now that we realize that we can always optimize our pocket change by giving it all to the cashier, we must figure out the real problem: how do we minimize the average number of coins in my pocket throughout the day?

Well, we must realize that no matter how much I have in my pocket, there will always be a 1/100 chance, after a transaction, of me having each amount between $0.00 and $0.99 in coins. Regardless of what I start with, there’s a fee that will leave me $0.03 in change, and a fee that will leave me with $0.64, etc. Using Shinn’s method (thank you cashier), the arrangement of this change is always optimal, so I can range anywhere from 0 coins ($0.00) to 1 coin ($0.01, $0.05, $0.10, $0.25) all the way up to to 9 coins ($0.94, $0.99). The average for all 100 possible values is 2.35 coins.

And since it doesn’t matter how much I start with, then the best way to get the lowest average for the day is… drumroll… to start with 0 coins in my pocket! If I start with 2 coins, the day average is 3.35 coins; if I start with 4 coins, the day average is 4.35 coins, etc., because I’m carrying more coins for the first half of the day. That is, Shinn’s theory states that the average number of coins post-transaction is fixed; the only way to minimize the day’s average is to minimize the coins I’m carrying pre-transaction!

So I’ve been doing it correctly all this time. The answer is: 0 coins.

Loose Change Puzzle, Part II

But this introduces a second problem. Sure, I’ve been unwittingly using the optimal method all these years, so that I have the least change in my pocket at all times… except that all these years I have been only receiving change!

In fact, averaging all the 100 possible intakes, each day I begin with 0 coins and come home with 4.7 coins! Ugh!

Now, we also know that to carry around $0.99 is the best way to get rid of change, because you can cover any amount and get rid of all those coins. I’d begin the day with 10 coins (you need 4 pennies, 1 nickel, 2 dimes, and 3 quarters to cover every amount up to $0.99), but on average would come home with -4.3 coins (got rid of 4.3 coins)!

So, new puzzle: What is the optimal coin combination to carry, where the fewest coins would get rid of the most coins? I guess this problem is weighted, because while 10 coins gets rid of the most, carrying 10 coins every day is undesirable. Hmm… How would you even weight it to calculate which answer is best?