Originally Posted by ColinsMum
The Wikipedia article on this is good:
http://en.wikipedia.org/wiki/Change-making_problem
Notice that it's a design feature of the particular coin system of the US that the "greedy algorithm", always picking the largest coin that will fit in the amount left to make, will work, and it is not obvious that the coin system has this useful property. The people who jumped at the solution provided by the greedy algorithm in these particular cases - how did they convince themselves and other people that they'd actually solved the problem, i.e. that there couldn't be a smaller set of coins that would add up to the same amount? It's not as hard to prove that an individual solution is optimal as it is to prove the general case, of course, but it still needs to be proved in each case (if you haven't either proved, or I suppose been given permission not to prove, the general case). Did they do it?

It wouldn't surprise me if the students who did less well at this problem were actually showing better mathematical understanding, i.e., understood more about what they needed to do to solve it!

The "greedy algorithm" would work when, every higher-value coin is an exact integer multiple of every lower-value coin, then in this case, each higher-value coin can represent an exact number of each lower-value coin, and consequently the higher the value, the less number of coins necessary. This is only an elaboration of the concepts of integer multiplication in probably grade-2 math, which shows that the "greedy algorithm" would work for the sets of coins {1c, 5c, 10c, 50c} or {1c, 5c, 25c, 50c}.

Now for the mixture of 10c and 25c, (a) "greedy algorithm" would work at or above, 5* 10c= 2* 25c= 50c, because of the concepts of integer multiplication again; and (b) "greedy algorithm" would also work below 50c for the set of coins {1c, 5c, 25c}, because of the concepts of integer multiplication yet again, with the modification that every pair of 5c canbe replaced by one 10c.

So the entire line of reasoning is within the concepts of integer multiplication, i.e. if those kids have really mastered grade-2 math, let alone already in grade 3, they should have no problem in understanding or even discovering the "greedy algorithm" on their own.