### No Need To Lose the Battle

In her recent post Tanya Khovanova bitterly complained of the difficulty the current spread and popularity of the Web and the social networks pose for successful teaching of students to *think*. A student nowadays can easily find online a solution to the puzzle he or she was supposed to rack the brain over and benefit from that exercise.

(In passing, I totally disagree with Tanya's thesis that "People who think make better decisions, whether they want to buy a house or vote for a president." That's factually wrong. This would be rather presumptuous to assume that the ones who disagree with one's choice of a president give their vote thoughtlessly. I am certain Tanya did not mean that.)

There are ways and ways to teach - I am reluctant to use the word "thinking" but rather - problem solving. Solving a problem starts first and foremost with posing a problem. Years ago I wrote about "mathematical droodles" - interactive activities that were supposed to lead the student to a formulation and a better grasp of a problem without explicitly articulating what it was about. In the same spirit, James Tanton just published two books, Without Words and More Without Words.

There is no much harm done by making solutions to puzzles available to students, though preferably not right away. There are even books of puzzles that come with solutions, e.g., Problem Solving Through Recreational Mathematics by Bonnie Averbach and Orin Chein.

It also useful to ask students to explain how they arrived at the solution - their train of thought that finally stopped when the solution took shape. A teacher may also demonstrate such process with all possible missteps and second thoughts. For example, Thimothy Gowers - A Fields Medalist - has recently demonstrated "live" his thought process by tackling one of IMO problems. Mike Lawler threw the gauntlet to other mathematicians to follow in Gowers' footsteps by offering to document their solving of a problem from the latest European Girls' Mathematical Olympiad. I even made an attempt to answer Mike's call.

And finally for this blog, it is worth remembering the last step of George Polya's paradigm for problem solving: *Looking back*. Is there another solution? Is it possible to modify the problem in a meaningful way?

Now I am going to quote Tanya's puzzle and solve it but only after offering a modified puzzle.

A sultan decides to give 100 of his sages a test. He has the sages stand in line, one behind the other, so that the last person in line can see everyone else. The sultan puts either a black or a white hat on each sage. The sages can only see the colors of the hats on all the people in front of them. Then, in any order they want, each sage guesses the color of the hat on his own head. Each hears all previously made guesses, but other than that, the sages cannot speak. Each person who guesses the color wrong will have his head chopped off. The ones who guess correctly go free. The rules of the test are given to them one day before the test, at which point they have a chance to agree on a strategy that will minimize the number of people who die during this test. What should that strategy be?

My modification is twofold. First, it's exactly the same problem as above, with the only difference in that the hats come in three (or more) distinct colors. I know one strategy - along the lines of the original puzzle - that reduces the number of possible victims to a reasonably small number. I am still pondering whether there is a better strategy.

Second, the puzzle can be modified in additional ways. For example, what if, instead of naming his hat's color, the sage was allowed to declare something more complex, like, say "red or blue"? Would that help to improve the strategy? To this I do not have a ready answer.

What if before doing his job the executioner was required to say loudly "Oops!" Could this help to save lives in the multicolor case?

Time for a solution to Tanya's puzzle:

Information helps a person make the correct determination of his hat's color. The more information one has, the better are his chances to stay alive. The only information sages have is what they see in front of them and the calls of the people behind them. If the order of calls is not random, it should follow a certain plan, probably sequential hat naming. The first one in the line has no information at all, the last one has all the information available. It is sensible to suggest that the process should start with the last fellow.

What information does he have? The number of hats of a certain color in front of him. The person in front of him has he same information minus one hat. If they agreed on a strategy of counting, say black hats, and the last one could say "27", the fellow in front of him would be immediately able to determine the color of his hat. If he sees 27 black hats in front of him, his hat is white. If he sees 26 black hats, his hat is black.

The "Aha moment" comes with the realization that there is no need for passing around the complete count. The decision, the sages make, are binary "either or". The last one may simply say "black" to indicate that the number of black hats in front of him is odd, and "white", if it's even. Assuming the last one calls "black", if the next to last sage sees an even number of black hats in front of him, he may conclude that his hat is black, otherwise it is white. The fellow in front of him gets this information, sees the number of black hats in front of him adds to that the binary 0 or 1 for each of the two calls from behind and determines the color of his hat: if the result is 1, his hat is black; if it's 0, the hat is white.

Full information is thus passing successively from the back to the front of the line. The only one who risks a beheading is the last one, and will have to be chosen by a draw.