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.
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 ThinkGeek purchase.