This puzzle and its solution were kindly provided by Christopher Dowden.
The coloured hat exam
Three students have been put in detention by their evil maths teacher, Mr Chalk. The pupils (Alice, Ben and Chris) have been unfairly accused of not liking probability! Now they will all be expelled unless they can prove Chalk wrong by passing his bizarre test.
In a moment, the crazy Chalk will lead the students blindfolded to his secret exam hall, where he will place mysterious coloured hats on their heads. The blindfolds will then be removed, enabling the three pupils to see each other's hats, but not their own. Finally, the students will sit an exam with only one cunning question: what colour is your hat?
Of course, normal exam regulations will apply, so the students won't be allowed to communicate with each other in any way once they are in the hall. They only know that the colours will be red and yellow, and that all 8 possible combinations (RRR, RRY, RYR, YRR, RYY, YRY, YYR and YYY) are equally likely.
Alice, Ben and Chris will each be allowed to write one of three words "red", "yellow", or "pass". They will not be allowed to see each other's answers. If at least one student guesses his hat colour correctly and none guess incorrectly, they all win. Otherwise (i.e. if at least one guesses incorrectly or they all write "pass"), all three will be expelled.
The pupils are currently in the headmaster's office, waiting nervously for Chalk's arrival. This gives them a few precious minutes together to devise their strategy. They can see that if they decide now that Alice and Ben will both write "pass" and that Chris will write "red", then this will give them a 50% chance of winning (as this tactic will succeed if Chris is given a red hat and fail if he is given a yellow one, regardless of the colours that Alice and Ben have). Can they do any better than that?
Solution
A problem like this has recently been circulating around universities all over the world. At first sight, it appears that 50% is the best the students can possibly achieve. For example, if they decide that Alice will write "pass" and that Ben and Chris will both write "red", then they will only have a 25% chance of winning (since they will only succeed if Ben and Chris are both given red hats). The situation is exactly the same if they decide instead that Ben and Chris will both guess yellow, or that Ben will guess yellow and Chris will guess red, or vice versa. If they decide that all three will guess red (or any other particular combination), then this is even worse as they will only have a 1/8 chance.
There are other more complicated strategies. For example, one possible tactic would be for Alice and Ben to both write "pass", and for Chris to write "red" if he sees that Alice and Ben are both wearing red hats and "yellow" otherwise. However, this will only be successful if the configuration of Alice, Ben and Chris's hats are RRR, RYY, YRY or YYY, which is again only a 50% chance. There is no way that Chris can use the information he has about Alice and Ben's hats to predict the colour of his own.
It seems that the knowledge the students have about each other's hats is useless, but in fact this information turns out to be a crucial part of the optimal strategy. With the right plan, the pupils will actually get a 75% chance of winning.
An optimal strategy is as follows: if a student sees that the other two are both wearing red hats, then he should answer "yellow"; if he sees that the others are both wearing yellow, he should answer "red"; otherwise (if the others have different coloured hats), he should write "pass". The possible permutations of hat colours and guesses are:
| Hat colours of Alice, Ben and Chris resp. |
Guesses of Alice, Ben and Chris resp. |
Win or lose | ||||
| R | R | R | Y | Y | Y | L |
| R | R | Y | - | - | Y | W |
| R | Y | R | - | Y | - | W |
| Y | R | R | Y | - | - | W |
| R | Y | Y | R | - | - | W |
| Y | R | Y | - | R | - | W |
| Y | Y | R | - | - | R | W |
| Y | Y | Y | R | R | R | L |
It turns out that 75% is the best that three pupils can possibly do, but what if there were more than three of them? One possible strategy would be for all the additional students to always write "pass" and for Alice, Ben and Chris to ignore the hats of these extra people and answer in exactly the same way as before. Again, the students would only lose if Alice, Ben and Chris all had the same colour hat, so they would still have a 75% chance of winning.
Is there any way that the students can ever do better than 75\%? In fact, by using techniques from the world of coding theory it can actually be shown that if the number of people is equal to $2^k - 1$ for some $k$ (1, 3, 7 and 15 are all numbers like this), then an optimal strategy will give the pupils a $\frac{2^k-1}{2^k}$ probability of winning, giving the probabilities
| Number of students | Probability of winning |
| 1 | 1/2 |
| 3 | 3/4 |
| 7 | 7/8 |
| 15 | 15/16 |
| 31 | 31/32 |
| 63 | 63/64 |
and so on.
In general, if the number of students is not equal to $2^k - 1$, the optimal strategy and chance of winning are not known!
Fortunately, Alice, Ben and Chris were all extremely clever (and lucky), and they passed the test successfully. Mr Chalk was very pleased to discover that he had such bright students, and so they all lived happily ever after — until the next lesson.
This puzzle is treated in more detail in the book Impossible?, which has been reviewed in Plus.
About the author
This problem has recently been circulating around univerities all over the world. It was written up for Plus in this format by Christopher Dowden, who studied maths at Gonville and Caius College, Cambridge, and then Merton College, Oxford, where he recently completed a DPhil on random graphs. He is currently a postdoctoral research fellow at the University of Canterbury in Christchurch, New Zealand.
Back to main puzzle page