10.Jan.22

This one is a doozy.

When I was first introduced to this problem, I was on vacation with my family at Disney World. Imagine me, a grown man, standing in line at the Pirates of the Caribbean ride, getting his father to keep count on his fingers every time I tapped on his arm as I tried to piece out the pattern. I worked on it periodically throughout the rest of the day, including on a place mat at a restaurant with a crayon. That night, I figured out how to approach the problem in a way that satisfactorily answers the question. But since then, I've found more.

Join me on that journey, would you?

Part 1: The Physical Model

The first thing we need to figure out is how these coins break up.

Pennies do not break, so if we have a penny we've hit the end.

A nickel can only break into pennies.

A dime breaks into 2 nickels, and then each of those nickels can break into five pennies.

A quarter breaks into two dimes and a nickel; that nickel can break into pennies. But we could have also broken a dime into two nickels, and then broken those three nickels each into pennies. And further, we could have broken both dimes into four nickels, giving us five nickels each of which breaks into pennies.

So, from this, we can see a single quarter has 13 different ways it can be made using quarters, dimes, nickels, and pennies. To write out this list, I'll use the first letter of the coin in the combination and whenever there's a large number of that coin I'll write it as, for example, (5P) for "five pennies." Thus:

1. Q

2. DDN

3. DD(5P)

4. DNNN

5. DNN(5P)

6. DN(10P)

7. D(15P)

8. (5N)

9. (4N)(5P)

10. NNN(10P)

11. NN(15P)

12. N(20P)

13. (25P)

At this point we might recognize that the 99-cent problem would be way too big to brute force comfortably -- not too big to do it, just too big to want to do it. But there are some interesting things we might be able to see here.

Part 2: Recombination

If we follow this logic down, we see that every time we've broken all of the nickels into pennies, we recombined all the pennies back into nickels in the next step and broke one of the dimes.

If we continue this logic, we'll see that once we've broken all dimes and nickels, we won't have anything else to break -- unless we actually have another quarter, at which point we'll want to recombine all the pennies into as many dimes as possible!

By doing this, we never begin the problem with more than one nickel. Ever! (This fact will be very important later.)

One last detail: Let's say that in the example above we had not 25 cents but 26 cents. That extra penny would never actually contribute to the count of coin combinations, because you can't break it and it won't recombine into any of the coins we have that are all multiples of 5. So, we should always round down to the nearest multiple of 5 first.

So, we follow these rules of recombination, as shown in the flowchart below; and each time we follow a green, full-arrow-head path, we add 1 to our count of unique coin combinations:

Part 3: The Patterns in the Count

Now that we have a pretty efficient way of processing the breaking of these coins, we might start trying to find all the different outcomes for the smaller coin values. Let's see a few, shall we? (And remember, because extra pennies at the start don't affect the outcome, we'll only be doing multiples of 5.)

• • For 0 cents, there is exactly one way to do it -- with no coins. (Likewise, if you have 1-4 cents, since you can't break the pennies then the original setup is the only possible setup.)

  • For 5 cents, we'll have N and (5P), which is 2 ways.

  • For 10 cents, we'll have D, NN, N(5P), and (10P), which is 4 ways.

  • For 15 cents, we'll have DN, D(5P), NNN, NN(5P), N(10P), and (15P), which is 6 ways.

  • For 20 cents, we'll have DD, DNN, DN(5P), D(10P), (4N), NNN(5P), NN(10P), N(15P), and (20P), which is 9 ways.

Wait, hold on. Check out what's happening at the step when we start breaking nickels. We'll start at DNN for the 20 cent example:

1. 1. 1. DNN

      2. DN(5P)

      3. D(10P)

Now, check out (4N) from 20 cents:

1. 1. 1. NNNN

      2. NNN(5P)

      3. NN(10P)

      4. N(15P)

      5. (20P)

Including the line before we've broken those nickels, we get one new way for each nickel plus the original setup with those nickels!

Also, notice that when only one dime was broken we got 3 new ways, and when both were broken we got 5. The number of new ways increased by 2 after we broke the dime.

In fact if we go back to the start, DD, we see there are no nickels to break but DD is in fact 1 new way.

So now we can count by the number of dimes!

• • DD -- +1

  • DNN -- +3

  • NNNN -- +5

But, check out what happens when we start with a nickel, as is the case with 15 cents:

1. DN

2. D(5P)

3. NNN

4. NN(5P)

5. N(10P)

6. (15P)

By starting with a nickel in the first line, we actually get an extra coin combination before we break the next dime:

• • DN -- +2

  • NNN -- +4

Finally, what about quarters? When you break a quarter, you get two dimes -- but you also get a nickel! If you didn't have a nickel already, you have one for the next set of coin combinations. If you DID have a nickel already, then you would combine those two nickels into a dime. So whether we start with a nickel or not after breaking the quarter will actually alternate!

This is not a big problem, but it does mean we need to keep track of each broken quarter. Here's what I mean:

We'll make a chart, with a number of columns equal to the maximum number of dimes we can get from our original amount, including one column for zero. This will be our "broken dimes" count. Also, the rows in the chart will be the setup we get after breaking a quarter.

We will fill in the cells from left to right, stopping once we've reached the column that is equal to the number of dimes in that row. The first number is 1 when there are no nickels; and 2 when there is. Each cell after the first increases by 2.

Next, we add the rows, and then add those rows' sums, and that becomes the total number of combinations!

Let's check this out with 65 cents:

• In the first row, there's a nickel, so we start at 2. There's one dime, so we go up to the column that reads "1," adding 2 each time.

• In the second row, there's no nickel, so we start at 1. There's four dimes, so we go up to the column that reads "4," adding 2 each time.

• And in the third row, there's a nickel, so we start at 2. There's six dimes, so we go all the way to the end, adding 2 each time!

With this system in place, it's now much easier to find the answer and we can even attack the original problem: 99 cents!

(remember, we take off the extra pennies, effectively rounding down to the nearest multiple of 5)

HOORAY! WE FINALLY HAVE AN ANSWER!

... Oh, one more thing.

Part 4: Patterns in the Row Sums

Take a look at the QQQDD row. The sum is 9. Also, Q(7D) is 64. Those are both square numbers: 9 is 3² (3 × 3), and 64 is 8² (8 × 8).

Now look at the other two rows. QQ(4D)N is 30, and (9D)N is 110. 30 is actually 5 times 6, and 110 is 10 times 11.

2 dimes: 3 × 3

4 dimes: 5 × 6

7 dimes: 8 × 8

9 dimes: 10 × 11

3² when there were 2 dimes; 8² when there were 7 dimes.

5 times 6 when there were 4 dimes and a nickel; 10 times 11 when there were 9 dimes and a nickel.

If we call the number of dimes d, then we can immediately know what the values of each of these rows will be based solely on the number of dimes and whether or not there is a nickel:

With a nickel: (d+1)(d+2)

Without a nickel: (d+1)²

With this information, we no longer need the physical breakdown, the flowchart, or the table of data. We only need the quarter breakdowns!

So, for 95 cents, that's:

• • • QQQDD: 2 dimes, no nickel, therefore: 3² = 9

    • QQ(4D)N: 4 dimes + a nickel, therefore: 5 × 6 = 30

    • Q(7D): 7 dimes, no nickel, therefore: 8² = 64

    • (9D)N: 9 dimes + a nickel, therefore: 10 × 11 = 110

And then we just add those products and we're done!

Part 5: Dime Patterns in the Row Setups

But we're interested now in patterns, right? So, take a look at the number of dimes in the initial setups: 2, 4, 7, and 9. Maybe that's not enough to build a pattern off of, but we can maybe see there's something going on there. Let's see some more examples!

The number of dimes in each of the subsequent rows of our chart (which, let's remind ourselves, are the new setups we get after breaking a quarter) increases either by 2 or 3, and does so alternately -- if it increased by 2 the first time, it increases by 3 the next time, and then by 2, and then by 3, and so on.

Why? Because of the nickels! A quarter gives two dimes and a nickel. If there's no nickel from before, you only gain the two dimes overall from breaking the quarter; and if there was a nickel before, then you gain three dimes overall from breaking the quarter.

We can now know, based on the initial setup of the first row, how many dimes will be in every subsequent row; how many rows there are; and the values of each row using our formula above.

Using 95 cents as our example again:

• 1. • The number of rows is 95÷25 rounded up, which is 4.

     • The first row looks like QQQDD, which has no nickel. This tells us two things:

       • • 1. First, the number of combinations for this row will be (d+1)² which, since there are 2 dimes, ends up being 3², or 9.

           2. Second, the next row will have 2 more dimes than before.

     • We know that because row 1 had no nickel, row 2 will have a nickel. Also, we know row 2 will have 4 dimes. With a nickel, the value of row 2 is (d+1)(d+2), which is 5 times 6, or 20.

     • Since row 2 has a nickel, row 3 will not have a nickel and will instead gain three new dimes, putting it up to 7. Without a nickel, the row will be (d+1)², which is 8², or 64.

     • Since row 3 did not have a nickel, row 4 will have a nickel and will only gain 2 dimes, putting it at 9.. With the nickel, the row will be (d+1)(d+2), which is 10 times 11, or 110.

Looking at it in word form is a little much, sure. Let's make a new chart!