Thursday, June 20, 2013
Wise Men Don't Wear Hats
An emperor decides to give 100 of his philosophers a test. The philosophers will stand in line, one behind the other, so that the last person in the line sees everyone else. The emperor has 101 hats, each of a different color, and the philosophers know all the colors. The emperor puts all but one of the hats on the heads of the philosophers, one per philosopher. The philosophers can only see the colors of the hats on people in front of them. Then, in any order they want, each philosopher guesses the color of the hat on his own head. Each hears all previously made guesses, but other than that, the philosophers cannot speak. They are not allowed to repeat a color that was already announced. Each person who guesses his color wrong will get his head chopped off. If a color is guessed a second time, all the philosophers will have their heads 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?
Subscribe to:
Post Comments (Atom)
7 comments:
It is, sad to say, clear that the philosophers cannot escape this challenge without risk of someone losing their head. The philosopher at the end of the line has all the information available to any philosopher, and no means of getting at the lacking information -- specifically, which of the two hat colors he does not see is the one on his head.
So he will have to guess, with a 50/50 chance of being right. The philosopher at position 99 is now in a similar position. He can eliminate 98 of the colors he sees before him, and also eliminates the color he heard #100 call out, and makes a guess from the remeaining 2 colors with a 50% chance of success. Each of these wise philosophers keeps careful track of the colors that have been named, and will have to guess between the two colors which he does not see and has not heard.
So that's the lower bound on outcomes. The philosophers can improve their lot with some coordination. They memorize the list of colors in alphabetical order. They agree that the philosopher at the back of the line will look for the first color in the list, say aqua. If he does not see it, he has to guess by calling out aqua and take his chances. The problem is then repeated with 99 philosophers and 100 colors.
But it's likely that he will see aqua. By agreement, he waits one minute without calling any color. The philosopher at position 99 then repeats the process. If he does not see aqua ahead, he calls out that color. This time he will be right, since the philosopher behind him saw aqua. If #99 does see aqua ahead, he passes a minute in silence. #98 and the others in turn repeat the process, and eventually the aqua-wearing philosopher goes home free. Everyone hears aqua called out and removes it from their mental list, and the process is repeated from the back with the next color, azure.
As the number of philosophers is reduced, the risk of failure increases, but it is still much better than 50/50 for all philosophers, and never worse than 50/50 for any one.
The timing approach seems a bit arbitrary and tricky. Here's a technique that is more reliable, though its outcome may not be as good.
Whoever is behind aqua (the first color alphabetically) guesses first. Among the colors he does not see, he guesses the one that comes last alphabetically. If no one sees aqua, the last philosopher guesses aqua.
If the first guess was not aqua, whoever is wearing aqua can guess correctly and go home. In either case the arrangement is then repeated with the next alphabetical color.
If colors are distributed randomly, we expect that most of the even-number guesses will be correct, and the odd-number guesses will be 50/50, so roughly three-quarters of the philosophers will survive.
Nevermind that three-quarters figure.
Here's the situation. The philosopher at the back has the most information, so he may as well go first. But he has to guess between two alternatives; he can't be sure of guessing correctly. At the same time, he doesn't have any reason to prefer one alternative or the other, so he can make his choice in a way that conveys information to the next philosopher in line.
After #100 guesses, #99 will see 98 colors ahead, leaving 3 colors unseen. #100 called out a color, which cannot be mentioned again, so there are two colors for #99 to choose from. As with #100, he has no reason to prefer one or the other.
Philosopher #100 will choose between the two colors in a way that indicates to #99 which color to guess. #99, according to plan, will guess the color he doesn't see that comes next alphabetically after #100's guess (returning to the start of the list if necessary).
Suppose #99 is wearing orange. #100 does not see green or yellow. #100 will guess green, because the next color after green is orange. Whether #100 is right or wrong, #99 knows to guess orange.
Suppose instead that #99 is wearing yellow. #100 does not see green or orange. #100 will guess orange, because the next color after orange is yellow. #99 knows to guess yellow.
And finally, if #99 is wearing green, #100 does not see orange or yellow. #100 guesses yellow, so #99 knows to guess green.
After #100 and #99 are done, it is #98's turn. Eliminating the 97 colors he sees ahead and the two he has heard called out leaves two possibilities for his hat. He adds the color of #97's hat to make a list of three colors, and, like #100 did before him, #98 guesses the color which comes alphabetically before the color #97 is wearing, so #97 can survive.
If colors are distributed randomly, even-numbered philophers expect to survive at a rate of 50%, and odd-numbered philosophers all survive.
Through a side channel I have received nudges in the direction of a much improved strategy, which results in, at worst, two philosopher deaths.
The alphabetical list of colors is essential. To make the ordering simpler, we will replace the names of colors with numbers, so aqua is 1 and yellow is 101.
The philosopher at the end of the line, in position #100 will guess first. He drew the short straw and is prepared to sacrifice himself for the good of the rest. He will guess a color not because he thinks it is on his head, but to indicate to the others how they should guess, using the following procedure.
Starting from the front, he adds the color-numbers. So if the philosopher in position 1 wears blue, he adds 5 (supposing that "blue" comes fifth in the alphabetic list). The next philosopher wears green, so he adds 25. He keeps adding, and when the total exceeds 101 he subtracts 101 from the total to keep it in the range of 1 to 101. The final number is the total of all the color-numbers he sees, modulo 101. The color assigned to this number is the one he guesses for himself.
Most likely, it will be incorrect, and the last philosopher in line will breathe his last. But he has given the others an invaluable clue. The next philosopher, in position 99, can do the same calculation, adding up the numbers of all the hats he sees. He leaves his own hat color out, of course, and the difference between his total and the color-number he heard the last philosopher call out is the number of the color he wears. He calls out this color, and then the philosopher in position 98, and the rest in turn, can do the same calculation and divine the color of the hats they wear.
The only hitch is that some philosopher will probably find that his color is the one the #100 philosopher called out to get the process started. He dare not break the rules by repeating this guess, so he must call out the color which has not been guessed yet and he does not see ahead. He will be noisily executed, and the remaining philosophers will know not to use the number he guessed, but the number the last philosopher started with, to keep the pattern going.
In this way, 98 philosophers are guaranteed to live to plot against their emperor.
You can do a little better.
After reading Anathem, one can imagine the first philosopher taking a 50/50 guess at his own hat color, and chanting it in a sufficiently long and evocative way as to communicate the modulo information down the line, perhaps by counting tremuli.
If the strategy is to use the first guess to communicate the modulo, I don't see a way to enable anyone ahead wearing with the matching color hat survive. There is a chance that more than 98 will live, if by luck the modulo color happens to be the unused color (resulting in only one death) or if it matches the first speaker's hat (resulting in all saved).
My recollection is that you can guarantee 99 survivors, but I don't remember the method now. Maybe I'll pose this one to my apprentice and see what she does with it.
Post a Comment