Right now a puzzle is buzzing among mathematical circles concerning hats. It seems some mathematicians are pulling things out of a hat; for example, winning 3 times out of 4 in a situation that appears to be only 50-50. The puzzle concerns guessing the color of a hat on one's head; the idea is that you can see everyone else's hat but not yours. Actually hat problems are not new to mathematicians and we will look at two such problems, the hot one that has been making the rounds and another much older problem, and we shall see how one of these problems relates to "hangar queens", a concept from aviation maintenance.
Here is the first problem. In a room is a collection of people and a collection of red hats and blue hats. The master of ceremonies asks all the people to close their eyes. While this is done, the MC places a hat on each person's head. The people are told to open their eyes, and truthfully, the MC says that at least one hat is red. The people in the room feel that he is saying the truth.
The MC asks, "Does anyone know the color of their hat?" Silence. No one appears to know. So the MC repeats himself. "Does anyone know the color of their hat?" Again, silence as people shake their heads. No one knows. Again the MC asks the people if they know the color of the hat on their head. Again people shake their heads. Getting a little tired of repeating himself, the MC asks, "Does anyone know the color of their hat?" Instantly four people yell, "My hat is red!"
And indeed they are correct. They are the only ones in the room wearing red hats. Every one else is wearing a blue hat. How does that happen? The MC is repeating himself over and over again like a broken record and nothing changes so it seems that every time he asks the same question he is going to get the same answer: no one knows.
But wait. Things do change. The people learn that the others in the group don't know the color of their hats. And that changes the situation. Eventually, people can conclude that they are wearing red hats. How does that happen?
The MC says at least one hat is red. Suppose there is indeed only one such hat. There is a red-hat wearer and every one else has blue hats on. The MC asks, "Does anyone know the color of their hat?" The blue hat wearers don't know because they see a red hat and several blue hats, and that meets the condition of the problem, namely, that there is at least one red hat. However, the red-hat wearer sees all blue hats and concludes that since there is at least one red hat out there he must be wearing it. So he says, "My hat is red." In other words, if only one person is wearing a red hat, he finds out right away.
Now consider the situation in which two people are wearing red hats. The MC asks, "Does anyone know the color of their hats?" The blue hat people see two red hats and blue hats and can't conclude anything. The two red hat people each see one red hat and all blue hats, so they can't conclude anything either. So no one raises their hand. However, each red hat person sees another red hat person. He says to himself, "What if I had a blue hat on? Then that other guy would see only blue hats, so he would conclude right away that he had a red hat on. He didn't, though. Therefore, I don't have a blue hat on. I have a red one on." Of course the other red hat person reasons the same way. So when the MC asks the question again, both say that they are wearing red hats. Not only can this all happen, but people can think about it even before play begins by imagining that two people have red hats on and concluding that after two askings of the question, both will raise their hands.
Taking that into consideration, suppose there are three red hats out there. The red hat people each see two red hats. The others see three red hats. Each one of them reasons that if they have blue hats on, then the above argument will hold, and therefore the other two red hat people will say after two questions that they have red hats on. The MC asks the question. No one knows. He asks again. No one knows again. But after that second question, each red hat wearer thinks that the other two red hat wearers should have raised their hands saying they have red hats on. They didn't. Therefore each one of them concludes that they themselves must have red hats on. So the third time this happens, each one of them says, "I am wearing a red hat". Further, people think about this even before the game begins. This may be stretching things a bit, but let's suppose these people are all gifted logicians.
Now let's try four hats. After three rounds, no one could tell what color hat they had on. But each red hat person sees three red hats and concludes that they all should have announced that fact after the third question. They didn't, so they all conclude that they themselves have red hats on.
This reasoning can be continued indefinitely. This means that in a room of thousands of people, including exactly 1000 who are wearing red hats, supposedly the announcer would ask 999 times if people knew the color of their hats, without getting any response. The thousandth time he asks, a big roaring ruckus occurs, as all one thousand of these red-hat wearers say at the same time that they have red hats on. That's assuming each one of these people can quickly count 1, 2, ..., ,999, and say, "ah, 999 people out there are wearing red hats". But the logic still remains.
What is so remarkable about this is that exactly the same question, "Do you know the color of your hat?" is asked several times, and the answer to that question changes, even though not a single hat is touched! One would think, if I know that I have a red hat on, then I know that I have a red hat and if I don't, then I don't. But in this case, first people don't know the color of their hats,and then they do, and nothing new seems to have happened.
Of course something new has happened. People learn of each other that they don't know the color of their hats. And they are able to reason from this what the color of their own hats are.
To come up with a general theory for this problem, one can use information sets. For example, if four people have blue, red , blue, and blue hats on respectively, then Player 1 knows that the situation is either (blue, red, blue, blue) or (red, red, blue, blue), depending on the color of their hat. Player 1's information set is therefore:
{(blue, red, blue, blue),(red, red, blue, blue)}.Therefore, Player 1 can't conclude anything, since both elements of his information set are possible and Player 1 wears blue in one of the elements and red in the other. However, player 2's information set consists only of one element; it is {(blue, red, blue, blue)}, since the MC ruled out (blue, blue, blue, blue) and Player 2 believes him. This only element of his set has him wearing a red hat, so he says "I am wearing a red hat".
To cover the case of two questions, one needs to deal with meta-information sets. One needs to know the information set of each player as that player would envision it. For example, if the situation is (red, red, blue, blue) then Player 1's meta-information set is:
{
It consists of four elements. The first is Player 1's original information set. The other three elements are themselves sets of information sets, one for each of the other players. There are two information sets in the Player 3 set, for example. The first information set is that of Player 3 if Player 1 has a red hat on, and the second one is that of Player 3 if Player 1 has a blue hat on.
This is getting a little complicated, but note that in Player 2's element of the set, the first information set of this element gives Player 2's information set in the case of Player 1 having a red hat, and the second set covers the case of Player 1 having a blue hat. Note that the latter is short an element because of the ruling out of all blues. Therefore Player 1 concludes that player 2 would announce if player 1 had a blue hat on. But if he does not, then Player 1 can eliminate that element, and the other element has for elements only situations in which player 1 has a red hat on. Therefore after two questions, Player 1 concludes he has a red hat on. With three hats on, people must reason about their meta-meta-information sets, so this quickly gets quite complicated.
Not only is the analysis complicated, but it can also get sticky. How long a period of time must pass before Player 1 can conclude that Player 2 does not know the color of his hat? Different assumptions as to what constitutes "long enough" can lead to someone asserting the wrong color for his hat. Suppose there are two people, A with a blue hat on and B with a red hat on and everyone else has blue hats on. On the second question, if A assumes that if after 5 seconds someone has not announced then he does not know, and if B thinks about the situation and after 7 seconds concludes he has a red hat on, then Player 5 will assume instead that he didn't know and will announce incorrectly that his hat is red. Perhaps the problem would flow smoother if people who don't know their hat color announce that explicitly. So after the first round, we may hear everyone say simultaneously, "I don't know". Then the analysis above works.
We conclude this hat problem by stating its underlying principle: Hearing that other people can't deduce the color of their hats can help one discover the color of one's hat, and repeating the same question over again does not always yield the same answer.
Let's go on to the other hat problem, the one that is burning up the mathematics world at the present moment, much as the "car and goats" problem did earlier. There can be any number of players for this problem also. Let's assume for the moment that there are three players; call them Art, Betty, and Charlie. The MC tells them to close their eyes, and then, completely at random, independent from the MC and from the three players and anything else, a hat is chosen at random. Fifty percent of the time, a red hat is selected to place on the person's head. Fifty percent of the time, a blue hat is selected. The players open their eyes. The MC then asks them each at the same time to either guess a color for their hat, or to pass. They can't collude with each other when the guesses are made, but they can consult each other and plan strategy beforehand. If someone guesses incorrectly, the players (who form a team; there is no competition) all lose. If no one guesses incorrectly and at least one player makes a correct guess, they win. They lose if they all pass. What's the maximum probability of winning the game?
One would think that it is better to keep your mouth shut. Every player that opens his mouth halves the group's chances of winning. But if everyone did that, they would all pass and lose. So it would seem the group can do no better than to have everyone except a volunteer pass and to have that volunteer simply name a color, as red. The group's chances of winning are then 50%, depending on whether the volunteer predicted correctly or not. It would seem hard to find a way of bettering the group's chances, considering that in a sequence of plays, each person must guess his hat color 50% of the time correctly and 50% incorrectly. Of course they can collude beforehand, and the players can observe the other two player's hat colors, but it would seem to be hard to use this to better the group's chances.
Surprisingly, it turns out that observing the other player's hat colors plus pre-game collusion can improve the group's chances of winning to 3 out of 4. Let's see if we can reason this out. Let's make some observations and assumptions:
| play | Art | Betty | Charlie |
|---|---|---|---|
| 1 | red | red | red |
| 2 | red | red | blue |
| 3 | red | blue | red |
| 4 | red | blue | blue |
| 5 | blue | red | red |
| 6 | blue | red | blue |
| 7 | blue | blue | red |
| 8 | blue | blue | blue |
The last two assumptions are not necessary to derive a 3/4 strategy, but it makes the analysis easier. Art needs to find a suitable response to his seeing two blue hats, for example. Suppose he chooses to guess blue in that case. Then Betty and Charlie will also play this same strategy, from assumption 3. If the MC happens to select blue, blue, blue, then all three will then say, "blue" and they will all be correct. This seems to be good. We want them to be guessing correctly, don't we?
Strangely enough, no. This is because the players can't buck the odds. By chance each player is doomed to miss about 50% of his guesses. It therefore follows that a correct guess is precious and should not be wasted. All that is needed is one correct guess to win. In the case above, two correct guesses were wasted. It is inevitable then that the corresponding incorrect guesses will come out later on and ruin the performance of our team.
This says the reverse strategy needs to be followed. It is so unintuitive that I want to state this explicitly:
That is, what the team wants is a round in which each one guesses wrong. Sure they guess wrong and lose, but for three wrong guesses, they lose only one round. If these were airplanes instead, they would strive to have an airplane with three things wrong with it instead of one thing wrong with each of three planes. And indeed that makes sense, since they can fly two more planes in the first situation than in the second.
This brings up aviation maintenance. Suppose a squadron of airmen have ten airplanes. Suppose something goes wrong with gizmo A of the first plane. Then they have only 9 working airplanes, for an operational availability of 90%. Then suppose gizmo B goes wrong with the second plane, where A and B have absolutely nothing to do with each other; e.g., an altimeter and a landing gear wheel. So does the squadron have two planes down and only 80% of its fleet flying? Not at all. They simply swap the parts B on the two planes, so now plane 2 is perfectly good and can fly.
Of course, plane 1 is still stuck in the hangar, with now two things wrong with it. If gizmo C then fails on plane 3, then again the aviators swap and our plane in the hangar has three things wrong with it. It may never fly again. It will dwell in this hangar forever and become what aviators call a "hangar queen".
Note how the hangar queen improves the effectiveness of the squadron. If all 10 of the planes come down with some problem such that the problems have nothing to do with each other, the aviators can swap around and fly 9 planes! The aviators pile all of the defects onto one unlucky plane, the hangar queen.
We do the same with the hat problem. It is inevitable that airplanes will develop defects, and likewise it is inevitable that the players of this game will guess wrong half the time. By piling all the wrong guesses on the same play or configuration, the "hangar queen", and carefully allocating only one correct guess on the other plays, the players can maximize their chances of winning.
It is natural to select all blue to be a hangar queen, since it is the only configuration that has zero red hats and three blue ones. The players agree to guess incorrectly if all blue turns up. Therefore, if a player sees two blue hats, he guesses red. Let's go farther. Let's set up all red as a hangar queen too. Then the players will guess blue if they see two red hats. So now if all red or all blue comes up, they ALL will guess the wrong color! That would be comical to see. The probability of all red or all blue coming up is 1/4.
But what happens if two blue and one red come up? That happens 3/8 of the time, since any of the players can have the red hat. In this case, the red hat person sees two blue hats and guesses red, which is correct! The other players should not interfere with this big success. Let him carry the ball for the team. Therefore they should pass. They each see one red and one blue hat. So the players agree to pass if they see one of each color.
Let's recapitulate this strategy:
This table shows what happens on the 8 possible plays:
| play | Art | Betty | Charlie | Art | Betty | Charlie | Outcome |
|---|---|---|---|---|---|---|---|
| 1 | red | red | red | guess blue: wrong | guess blue: wrong | guess blue: wrong | LOSS |
| 2 | red | red | blue | pass | pass | guess blue: correct | WIN |
| 3 | red | blue | red | pass | guess blue: correct | pass | WIN |
| 4 | red | blue | blue | guess red: correct | pass | pass | WIN |
| 5 | blue | red | red | guess blue: correct | pass | pass | WIN |
| 6 | blue | red | blue | pass | guess red: correct | pass | WIN |
| 7 | blue | blue | red | pass | pass | guess red: correct | WIN |
| 8 | blue | blue | blue | guess red: wrong | guess red: wrong | guess red: wrong | LOSS |
Despite guessing right 6 times and wrong 6 times, the group scores 6 wins and 2 losses, so that the probability of winning is 3 in 4.
One can analyze this problem using information sets as well. The analysis turns out to be simpler, in that meta-information sets are never needed. Suppose there are n players. Then there are 2n combinations of hats among the players. For three players, the table above lists the eight combinations. Each of the players will have as an information set two combinations. For example, if there are three players, and the hats dealt out were red, blue, red, then Player 2's information set is:
Note that in the play for three players, that if all red comes up, all the players guess blue and lose, whereas, as in this situation, two red and one blue come up, then the blue guy guesses blue and the others pass, so the group wins. The all-red combination was one of the hangar queens that we came up with earlier. Player 2's information set consists of one hangar queen and one non-hangar-queen. The optimal strategy calls for him to avoid saying the color that would produce the hangar queen. This way, if the hangar queen comes up, he is wrong; else he is right. So he guesses blue.
Therefore we need a strategy that would somehow provide a hangar queen to every possible information set. If we think of the combinations as points, then since information sets have two points each, and two points determine a line, therefore information sets are lines. If one connects all the lines and points together, the result is an n-cube. In this n-cube, if a point (combination of hats) is selected by the MC, then the players' information sets will be represented by the lines emanating from that point. For three players, this cube results:
The points are combinations of hats, and the lines are possible information sets. The two star-like objects represented by the colored edges are hangar-queen stars. They are sets of points that either are hangar queens or are adjacent to hangar queens. The hangar queen stars are outlined in red and blue respectively. Note that each point on this cube is a hangar queen or is connected directly to a hangar queen by a line (information set). If (red, blue, red) comes up, the point on the cube is adjacent to one hangar-queen point and two other points. The hangar-queen person guesses the other way, and gets it right, and the other two pass.
From this we can deduce the following rules for hangar queens:
Then the optimal strategy is to pass if both elements in your information set are hangar queens or if neither of them are, and to guess the non-hangar queen if one of the elements is a hangar queen and the other isn't. For the three-player case, the all blue hangar queen is adjacent to three other points, and the all-red one is connected to three points. This assigns each point to a star consisting of a hangar queen and the 3 points that are connected to it, a total of four points.
So in general to come up with the optimum strategy, one needs to partition the set of all combinations into disjoint hangar point stars. This is possible with 3 players since 3+1 = 4 divides 23 = 8. It does not work so well with 4, however, because 4+1 = 5 does not divide 24 = 16 evenly. The next n for which it works is 7, and indeed there is a way of breaking down the 128 points into 16 disjoint hangar queen stars of 8 points each. It turns out that there are some interesting relationships between this way and coding theory; in particular, to Hamming codes.
So we have come a long way. One hat problem becomes an exercise in cerebral (what's under that hat!) complexity, and the other one has relationships to aviation maintenance and to coding theory. So no matter what your endeavors are, keep your hats on and know their color!
Jim Blowers