Thursday, July 31, 2008

I've picked up a troll

Apparently I've picked up a troll. Now, normally I'm in favor of feeding trolls. They've moved onto the internet because their native environment has been destroyed by modern civilization. They used to live under bridges. However, modern bridges with cars and other loud noises are not conducive to their survival. I'm normally a bit of an environmentalist and should therefore support helping save the trolls. However, we all have our NIMBY moments and this one is mine.

Therefore, I have placed comments on moderation. I will need to approve any submitted comment before it appears. This does not change anything people need to do to comment but it does mean that their comments will not show up immediately when they are submitted.

Wednesday, July 30, 2008

More gratuitous promotion of family members

My twin has helped found a blog to comment on the Presidential debates. There are two other writers along with my twin. The entries are worth looking at, although Mark Samburg still uses the word "interesting" too much in his writing.

Since my twin has been used for commentary on Presidential debates by the New York Times, one can conclude that he might know what he is talking about.

Thursday, July 24, 2008

Mathematics education

In the United States there are long-running "math wars" over how to educate children in mathematics. CNN had a recent article about the latest skirmishes in these math wars. Now, I could spend an entire entry ranting about how people abuse the word "war" and I intend to do that sometime in the future. I could also write an entry about how the CNN article has no real news content and is hard to see as newsworthy. Instead I'm going to focus on the issues that the article raises.

The article focuses on how in certain schools teachers are deliberately not teaching the children how to do long-division and multiplication. However, frustrated parents are teaching their children how to do it, rather than focus on the "conceptual" understanding.

As someone who has tutored kids in math and has worked as a counselor at a summer program which teaches number theory to high school students, I have to side with the parents.

First, long-division is conceptual. It isn't that hard to understand what is going in the algorithm. And if a teacher cannot explain conceptually why long-division works they are not a very good teacher.

Second, conceptual in this sort of context often is a disguise for ad hoc methods that sometimes are shorter but in general will not be efficient. For example, to quote from the article "When a parent is asked to multiply 88 by 5, we'll do it with pen and paper, multiplying 8 by 5 and carrying over the 4, etc. But a child today might reason that 5 is half of 10, and 88 times 10 is 880, so 88 times 5 is half of that, 440 -- poof, no pen, no paper." This works fine, but what if I asked you to multiply two 3 digit numbers? Or 4 digit numbers? Can you easily use such methods then? If you cannot do that, then you do not have a true conceptual understanding of the content in question.

Third, there's an issue of causation v. correlation. People who are good at math use such short-cuts all the time when they are available. But they do that because they are good at math. That does not mean knowing how to use those tricks will make you good at math.

Fourth, many more advanced ideas depend on long-division and multiplication. For example, what if you want to understand how to multiple or divide in another base? Or what if you want to divide polynomials, or to do arithmetic in more abstract rings like Z7[x]? The "conceptual" understanding will not help much there. But having a good understanding of how to do division and multiplication the "old-fashioned way" and understanding why they work will help a lot.

There's also one problem that bothers me which has little to do directly with the math at hand: Some parents in the article report that they feel like they are being "rebels" for teaching their children. There is something seriously wrong when parents providing additional education to children are made to feel unwanted or to feel like they are doing something wrong. We have serious problems with parents not being involved in their kids' education. We don't want to discourage the good parents who are willing to help out simply over pedagogical disagreements.

Friday, July 18, 2008

Gratuitous Promotion of Family Members

My twin has a blog entry on the recent Israeli-Hezbollah prisoner swap which I strongly recommend reading. Aaron argues that the swap is a bad thing for the rule of law. I don't agree with the entry entirely. For example, I think he overestimates how much the swap damages U.N. authority and credibility (I don't think the U.N. has enough to distance to fall for this to matter much) and have a few other small criticisms but it is a thought provoking piece that you should check out.

Edit: I modified the above slightly to reflect that Aaron is arguing that the swap is bad for international rule of law rather than necessarily bad overall.

Wednesday, July 16, 2008

"Jim Robinson" is on the terror watchlist.

According to a recent CNN article, Former Assistant Attorney General Jim Robinson is on the terrorist watch list. I'll be honest: I had never heard of the guy prior to this. But here's the real issue: there might be people out there who don't mind if people with names like "Muhammad" can't get on U.S. airplanes, but everyone should be concerned if there are serious inconvenience to people with names like "Jim Robinson." That's right, this list is harming nice American Protestants with good, old-fashioned American names. Are you irritated yet?

Tuesday, July 8, 2008

Prisoners, Information Transfer, and the Axiom of Choice

The following entry is courtesy a variety of people. I believe that I heard the initial version of this riddle from my twin. The follow-up to infinitely many people is due to Erick Knight. Note that since I’ve noticed that I’m not very good at remembering to post follow-ups to puzzles I post I am just going to include the solutions in this post.

Initial riddle: Suppose there are a hundred prisoners. They are in a room and told that they will be all lined up so that the first one can see the next ninety-nine, the second one can see the next ninety-eight but not the first person, the third one can see the next ninety-seven but not the first or second, and so on. Each one will have placed on his head a black or white hat. The first one gets to shout out “black” or “white” so that everyone in the line hears. Then the second one shouts out “black” or “white”. If everyone shouts out the same color as the hat that that person is wearing then they will all get to go free. What is the best strategy for the prisoners? Remember, they are able to communicate before hand but once in can only say “black” or “white”. And no using stupid tricks like delaying when they say it to communicate more information.


The first person counts the parity of all hats they see, with black hats as 1 and white hats as 0. If the result is odd they black and if the result is even they say white. Each person after that one will then know what their hat is, since it must preserve parody with all the hats before and after them. Thus, they will get 99 hats correct and will have a ½ chance getting the first hat correct.

Exercise: generalize this to n different hat colors.

Now the part due to Erick Knight:

Suppose we have the exact same problem as before, but there are countably infinite prisoners each wearing a black or white hat (so there’s a first prisoner, a second prisoner, a third prisoner and so on). How can they assure that they at most finitely many people will not say the correct hat color. You may assume that the prisoners are able to see everyone in front of them.
Ok, the solution to this is unbelievably cool. Again, denote a black hat by 1 and a white hat by 0. So every possible string consists of some strings of 1s and 0s. Now, define an equivalence class on strings as follows: two strings are equivalent if they agree for all sufficiently far off digits. So for example, 010010000000000000... Is equivalent to 000000000… Now, from each such class pick a representative string, and remember it. When the prisoners are lined up each prisoner can see the string in front of him, and can recognize that as being in some equivalence class. So all the prisoner does is consults which representative string from that class they choose, and picks whichever 0 or 1 corresponds to his current position. Using this method, at most finitely many prisoners will get it wrong, because otherwise the string in question would not be equivalent and would thus not be a representative of that equivalence class.

Ok, isn’t that bizarre? It doesn’t even require any actual communication among the prisoners except at the start.

There are a number of objections to this solution: I will note three of them and discuss one of the more interesting ones in more detail:
Objection 1: People cannot look at infinite strings of data in finite time.
Objection 2: People cannot store all the representative strings (exercise so that the set of representative strings is uncountable).
These two objections are uninteresting, because even if one accepts them it isn’t at all clear why beings able to do these things should be able to get away with this. At best it is non-intuitive.
Objection 3: This is the interesting one: Who said I can pick representatives? In fact, in order to do so I need to use the axiom of choice, which says essentially that if I have a collection of disjoint non-empty sets I can pick one representative from each. This seems intuitive but the axiom can lead to strange results and some mathematicians do not accept the axiom. This puzzle gives a starting groundwork for appreciating that the axiom of choice although intuitive is strange. I hope to discuss the axiom of choice in more detail in a later blog entry.