Many thanks to everyone who sent a solution in to this week's puzzle. Both Max and Nora were anxiously awaiting results, and pored over them as they arrived. Okay, so maybe they weren't poring over them as they were arrived, but at least they were happy to see their pictures on the GeekDad website, and to be mentioned by name in a Puzzle of the Week. In either case, here is the puzzle as posted on Monday:
Max and Nora were counting their savings jar change recently, and Max was showing Nora that there were a few ways to make $0.10. There were four to be exact — using only a dime, two nickels, one nickel and five pennies, or ten pennies. That got me thinking — there has to be a "how many ways to make change" puzzle in there somewhere. However, the standard "how many ways to make change for one dollar" solution was easily searchable (142 million results?) and would not be a worthy GeekDad puzzle. The fact that there were four ways to make a total of ten cents got me thinking…
That quick search engine search told me that there were some 293 ways to make change for $1.00 (using the standard US coin denominations — silver dollar, half dollar, quarter, dime, nickel, penny.) Dividing the number of ways to make change (293) by the number of cents (100), we get the value 2.93. In Max’s example above, we have 4 ways to change 10 cents, and four divided by ten is 0.4. Clearly, some of these values will be over 1, and some under 1 — and maybe some exactly at 1.
For your shot at this week’s $50 ThinkGeek gift certificate, determine the counts of change amounts from $0.01 to $1.00 that are under, over, and exactly at their counts of being made into different sets of change.
There were a variety of different ways that this problem was solved -- most everyone wrote or borrowed a little bit of code. C, C#, and Javascript were popular choices for coding languages. The counts for each money amount ($0.01, $0.02, $0.03, etc.) turned out to be a fun little "step function" where a new value was seen every five cents. This makes intuitive sense, as the $0.05 increment is the smallest amount of change that can be made, as it is the first non-unit coin type -- the nickel. There is only one way that you can represent $0.01, $0.02, $0.03, and $0.04, but two ways to represent $0.05.
Graphically, the count-per-cent-value step function can be seen in the chart to the right. Each new value divisible by $0.05 allows for more permutations, and the function is an increasing function -- it always remains the same or increases as the change value increases.
The red line on the chart is a 1:1 line, and you can see it crosses the blue count step function curve at three points; two of these are on an integer value, where the number of ways to make change for a given amount of money is equal to the worth (in pennies) of that amount of money. These values are:
- $0.01, with just one way to make change
- $0.50, with 50 ways to make change.
The 3rd time the lines cross, they don't hit an integer value; they cross between $0.54 (50 ways to make change) and $0.55 (62 ways to make change.)
The blue line is under the 1:1 red line for the 48 values from $0.02 to $0.49, and then again for the 4 values from $0.51 to $0.54 for a total of 52 values. The blue line is above the 1:1 red line for the 46 values from $0.55 to $1.00. With the two exact matches at $0.01 and $0.50, all 100 values are accounted for.
Congratulations to Jamison Hope for submitting a correct answer and being the randomly chosen winner of this week's $50.00 ThinkGeek gift certificate. For everyone else that submitted an answer or simply put up with my chart, please feel free to use the code GEEKDAD59MJ to save $10 on your $50 ThinkGeekpurchase.
