The Wikipedia article on this is good:
http://en.wikipedia.org/wiki/Change-making_problemNotice 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!
