Wednesday, March 2, 2016

Making Change and... Partitions?

Today’s math fun involves portions of yesterday's, but with a few more steps.  It may also—dare I say it?—involve partitioning!  I might be using the word partitioning in an incorrect way, and if so, then pardons please, (also, please let me know).  The question is, what are the fewest number of coins you need to make change for up to a dollar.

Here's how I worked, using an iterative algorithm, (fancy words for: "I'm going to use the same trick over and over").  It was all about granularity of coins, and getting quickly from one amount to the next.  The quickest way, (where quick is defined by using the smallest number of coins), to get to a large amount of change is with large coins.  So, as we move around within 99 cents, the biggest step we can make is with a half dollar. Using yesterday’s method, we can fit one half dollar into 99 cents.  That leaves us with 49 cents left move around in.  The quickest way to make progress within that interval is with a quarter.  We can only fit one quarter into 49 cents.  That gives us our next interval which is moving around within 24 cents.  We use our next biggest coin, a dime, and figure out we can get two of those into 24 cents.  Within the remaining 9 cents, (the space a dime can't make up), the quickest way to move is with a nickel.  One of those will fit.  That leaves us a four cent interval to move in.  We can fit four pennies into that, and we’re done!  So, the answer winds up being

1 50 cent piece
1 quarter
2 dimes
1 nickel
4 pennies.

The next step, would be to prove that I'm correct, but how?

No comments: