Why is a raven like a writing-desk?
I recently learned about The Hat Puzzle, which is a surprisingly tough little conundrum that goes like this:
N people walk into a room and a hat is placed on each person’s head. Each hat is either red or blue, and the chances that any given hat is red are 1 in 2. Each person can see the colours of everyone else’s hat, but not the colour of their own. While in the room with the hats, no one is allowed to communicate with each other in any way at all. Everyone is then lead into separate rooms, and asked the colour of his or her own hat. Each person can choose to answer or to pass. If at least one person answers correctly and no one answers incorrectly, the whole group wins. How do you maximize your chances of winning?
The naive solution (before entering the room, pick one person who will guess Red and have everyone else pass; chances of winning are 50%) seems easy enough, but there are more complicated solutions that do better. For instance, with 3 people, you can win 75% of the time: if your comrades have the same colour hat on, guess the other colour. If they have different colour hats, pass. The only time you lose is when everyone has the same colour hat. Note that a person who chooses to guess the colour of their hat is still wrong half the time (i.e. probability isn’t broken), but we’ve spread out the occurrences of correct answers and bunched all the wrong answers on top of each other. Apparently you can use Hamming Codes to win with odds N out of N+1 when N is 1 less than a power of 2, but I haven’t seen an explanation of how that works yet.
Apparently, this is an unsolved problem for all other N, though. I have written a Java program to use a brute force method to find the solutions, and it easily verified that the best you can do when N=3 is 75% (using the strategy described above). The problem with this brute force solution is that its running time is O(2^n * 3^(n*2^n)), which makes it rather unwieldy. I’ve started running the program to solve the N=4 case, and I hope it will finish by tomorrow afternoon. edit: I dramastically misunderestimated the time needed to run this program. It will hopefully be done by Thursday. I will not use it to find the solution for N=5.
As usual for subtle and tricky topics, the Wikipedia page is wrong in subtle and tricky ways (at least, it was when I wrote this), so don’t bother looking for more information there.
(Edit: I continue working on this in part 2)
The Hamming codes are [2^r-1, 2^r-1-r, 3] binary linear codes. Let (n = 2^r-1) be the number of people (hats) — this is also the length of the codewords. Let (k=2^r-1-r) be the number of codewords (error-free messages in the Hamming code). It is a property of Hamming codes that they are perfect — e.g. every point is either a codeword, or within [floor((3-1)/2) = 1] Hamming distance of a codeword.
The short explanation is that because the Hamming codes are perfect, all of the 2^n assignments of hats are either a codeword or within 1 flipped hat of a codeword. If you assign everyone a bit in the word, the algorithm is “if what I see could be a codeword, I set my bit so that it’s not a codeword”. Else, I pass. The only case where everyone passes is if you’re on a codeword, with probability 2^k/2^n which ends up being 2^(-r) e.g. 1/(n+1).
Ooh, nice idea! So, if the bits of the whole group represent a valid Hamming code, everyone guesses wrong together. Otherwise, everyone passes except the one person who could bit-flip themselves into a Hamming code, who guesses correctly. and since there are n non-Hamming numbers for every valid Hamming number (since there are n ways to be off by 1 of the n bits), the chances of success are n out of n+1.
That’s very clever. Thanks for explaining!