Gifted Issues Discussion homepage Forums General Discussion hours spent studying in high school and college

Extending a sample size of 4 Asian kids into an Asian stereotype? Wow........ I personally know of several Asian kids who solved this type of problem at age 5, without any help whatsoever. Being good in 3rd-grade math, should at least be about knowing how and when to use addition and subtraction, and more......., instead of merely doing addition and subtraction as a mechanical process, which can even be done by sight at age 3. Those Asian kids you mentioned don't fall into this category of "being good in math". And most likely, they will have trouble pretty soon in learning to do long-form division, which would follow a similar line of reasoning as this type of problem.

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.

I didn't say that a proof wasn't in principle accessible to them; I said that it wasn't obvious. In particular, if the students in question didn't indicate that they were going through some such proof - and surely, previous posters would have remarked on it if they had - then I don't believe they had a proof in mind. (In fact, if your kids go to a school where many 3rd graders would be capable of producing one, I expect many people here would be envious!)

Admittedly, now that I reread the earlier post, I see that some of the students described as being weak at problem-solving apparently didn't understand what they were being asked to do, which speaks against my hypothesis that they might actually have had a better understanding of the problem than those who leapt at an algorithm and (I surmise) didn't engage with the question of why their algorithm worked.

Incidentally, DH pointed out to me that the UK's pre-decimalisation coin system had the property that the greedy algorithm did not always work.

OK, I follow how that's done, but without an explicit explanation of how to do it, I don't think I'd have ever come up with it.

Given that the Wikipedia entry on "greedy algorithm" itself says "Greedy algorithms mostly (but not always) fail to find the globally optimal solution," I'm not sure I see any value in teaching it as a rote problem-solving technique to kids, other than as a parlor trick that coincidentally happens to always work with US coins.

Well... that may be true, but if you don't know how to solve a packing-type problem - or, come to that, a problem of any other kind where it isn't clear how to solve the whole problem, but you can compare possible next steps and see which makes most progress in some sense - a greedy algorithm is a jolly good place to start. If nothing else, thinking about how such an approach can fail may give you insight into the problem. For giving change specifically, it works for pretty much any modern system of coins; the fact that it didn't work for UK pre-decimalisation is an anomaly.

Discussed this with DS and his main contribution was amusement at the name. He couldn't believe that a greedy algorithm was really so called because it's greedy, rather than because it was invented by someone called Grede!

As I illustrated in my earlier message, the entire line of reasoning is within the concepts of integer multiplication in probably grade-2 math. So the label of "being good in math" and especially for the kids already in grade 3, should only be reserved for those knowing how and when to apply such concepts in different types of problems. And even more so, because this is a gifted forum and presumably we may steer the discussion toward gifted kids.

Then how do I know at least several Asian kids can solve this type of problems at age 5, without any help whatsoever? Simply because I asked them to explain after arriving at the correct answers. They may not have illustrated the line of reasoning as I did in my earlier message, although in a more clumsy 5-year-old manner. But as long as they can point out that 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 are necessary, then they have implicitly discovered the "greedy algorithm" on their own. And incidentally, these kids have been studying grade-3 math at the age of 5 and apparently have mastered grade-2 math.



I suppose we may accept as fact that most 3rd-graders don't master grade-2 math at all, and many people here supplement their kids with more advanced curriculum, than merely depend on the school.

From a math perspective, the line of reasoning behind solving problems, is far more important than the mechanical process. This is one reason that some people avoid Kumon, because of the excessive repetitions. Many people even find Saxon overly redundant. But from a practical perspective, everybody can learn how to use coins, without really understanding the math involved.