I guess since my previous hat color guessing problem was so popular, I might as well talk about the other one I know. However, this one isn’t meant to attack the foundations of mathematics. The problem is as follows:
Three people are sitting in a circle. Black or white hats (50% chance of each) will all be placed on their heads, and they will be able to see everyone’s hat color but their own. They will all simultaneously write down on a piece of paper either “Black”, “White”, or “Pass”, trying to guess their own hat color. All the people collectively win (whatever that means) if at least someone guesses their hat correctly and no one guesses incorrectly. They lose if anyone guesses incorrectly, or everyone passes. If they can agree on a strategy beforehand, what is their best chance of winning?
Again, there is the problem that no information can be conveyed to someone about their own hat color, so they would seem to be guessing blindly (talking and facial expressions are prohibited). However, they can still win 75% of the time. Figure it out!
Once you solve the easy version of this puzzle, the harder version is with larger numbers of people. As a partial spoiler, stick to 
The trick to the puzzle is realizing that, even though any specific person who elects not to pass has only a 50% chance of being right, the strategy can be chosen so that the wrong guesses are all concentrated into a small number of possibilities. That is, because you only need one right guess to win and multiple wrong guesses don’t make a loss worse, the strategy should attempt to make as many people wrong simultaneously if anyone is going to guess wrong.
The three-person case makes a good example. Consider the following strategy:
If you see two hats of the same color: Guess the opposite color.
If you see two different hat colors: Pass.
What happens? It’s not hard to write down all the possibilities:
3 black hats: Everyone sees two black hats, and guesses White. Everyone is wrong.
2 black hats, 1 white hat: The people in black hats see both colors and Pass; the person in the white hat sees two black hats and says White. One person is correct and everyone else passed.
1 black hat, 2 white hats: This is identical to the previous case, with colors reversed. Its a win.
3 white hats: This is identical to the first case, with colors reversed. Its a loss.
So unless all three hats were the same color, everyone won. However, the chances of all three hats being the same color is only 1 in 4, so its a win 75% of the time. Notice that the key was getting everyone to be wrong at the same time, but only having one correct guess in winning situations.
Ok, what about more people, say, 
Since the optimal strategy seems to be when all the wrong guesses happen simultaneously, we need to agree on some sequences that will be the wrong sequences, that is, the scenarios where everyone will guess incorrectly. How does this work? Say 
The general strategy if you have a whole bunch of wrong sequences is for everyone to look around, and:
If it looks like you might be in a wrong sequence, guess the opposite possibility.
If you are definitely not in a wrong sequence, pass.
(Note that we are assuming that no two wrong sequences differ by a single digit, so that there is always an ‘opposite possiblity’) How well does this strategy work?
It loses every wrong sequence.
It wins every sequence that differs from a wrong sequences by exactly one digit.
It loses every sequence that differs from every wrong sequence by at least two digits (since everyone passes).
So what we want is a collection of wrong sequences that are evenly spread out amongst the possibilities, ie, we want to ‘cover’ as many possibilites as possible with the fewest number of wrong sequences.
This is actually a problem that real people care about, even some who don’t wear hats. This is (roughly) the problem of finding an error correcting code. Sometimes, one computer will be sending another computer information in the form of a sequence of 1s and 0s, and by some fluke a single digit will get flipped. The goal of error correcting codes is to turn the sequence of 1s and 0s you want to send into a longer sequence, which has the property that the receiving computer can tell if a digit got flipped and repair it.
A silly example is the Tripling Code, where if what I want to do is send you 
What does an error-correcting code look like? Well, we agree ahead of time upon which possible sequences are the codewords (ie, the ones that are correct), and how to turn them into the messages we really wanted to send. Then, if you get something that differs from a codeword by exactly one digit, you know how to correct it (this is assuming that the codewords are far enough apart that there is only one close one). So the goal for making an efficient code is to pick codewords spread apart evenly enough that as many possible sequences are exactly one away from a codeword. This is exactly what we were looking for with our ‘wrong sequences’, even though the names were different.
Therefore, we can invoke some fancy error-correcting codes to find the optimal hat guessing strategy. In particular, if the number of people/length of sequence is
However, this only solves the problem for a very specific number of people. What about other numbers? Theres a complication in these cases, in that its impossible to have a perfect code. That is, it is impossible to choose wrong sequences so that every possible sequence is either wrong, or one digit away from exactly one wrong sequence.
We can ask what the nearest possibility to a perfect code is, but its not clear which way to be less than perfect is optimal:
1) Having some of the correct guesses overlap, that is, having some wrong sequences differ by 2 digits.
2) Having some sequences which are lost because everyone passes.
3) Most significantly, moving away from the ‘wrong sequence’ strategy.
The last one, which I would guess is the correct way to proceed, is bad because the tools from computer science become useless rapidly. I really have no idea what the optimal solution looks like here.
The Everything Seminar 
September 20, 2007 at 7:49 am |
Now that’s really nice. I’ve seen this hat problem, but not the connection to ECCs.
September 27, 2007 at 4:11 am |
I’ve written about this (in a long currently unpublished monograph on mathematical Disinformation Theory co-authored with Prof. Philip V. Fellman at Southern new Hampshire University).
The connection with Error Correcting Codes (which I took as a Caltech course long ago from Golomb, using Berlekamp and other texts) is explored at:
The Rényi–Ulam pathological liar game with a fixed number of lies
See, for example:
www-rohan.sdsu.edu/~vadim/epy.pdf
or
http://math.berkeley.edu/~berlek/stat.html
Berlekamp [1968] studied a closely related problem, which was subsequently independently popularized by Stan Ulam and became known as “Ulam’s problem”, or “20 questions with lies”. In this problem one player selects an object at random from a set of M possibilities. His opponent attempts to discover the object by asking n yes-no questions, sequentially. The answerer is permitted to lie up to e times. What values of M, n, and e, are wins for the selector, and which are wins for the questioner? Berlekamp essentially solved the problem for large values of the parameters. Let R = lg M/n, and let f = e/n. Then the boundary values lie on the curve f(R), which is depicted above. Although Berlekamp’s paper was often cited in work on “Ulam’s problem” in the 1980s and early 1990s, the last half of the paper was never carefully read. Ulam popularized two values of M, namely 1,000,000 and 220. For both of these values of M, for each e, Ray Hill subsequently determined the optimum value of n precisely. Des Jardins then extended these precise results much further. For many values of n and e, he was able to determine the maximum value of M to within one or two objects.
For 3 lies, it was noticed that the solution was identical to a well-known ECC optimal for correcting 3 bit-errors per codeword.
E. R. Berlekamp, “Block Coding for the Binary Symmetry Channel with Noiseless, Delayless Feeback”, pages 61-68 in Error-Correcting Codes, edited by H. B. Mann; John Wiley and Sons, New York, 1968; Math. Rev. 38:3072.
E. R. Berlekamp, “The Performance of Block Codes”, Notices of the AMS, January 2002, 17-22.
Claude Elwood Shannon, Collected Papers, edited by N. J. A. Sloane and A. Wyner, IEEE Press, New York, 1993, pages 385-454.
David DesJardins, UC Berkeley math PhD thesis, Fall 2001.
or
April 25, 2008 at 5:15 pm |
Ouch… i only came to this page after one evening and one afternoon thinking about it and realizing its connection with ECC in the case n=2^k-1 🙂
I see that a lot of study has been done for other n values, but what if the number of colors is more than two? At a first look, this problem seems very difficult, and i have not been able to find an answer even for special values of n. Do you know if this has been studied before?
Thanks!
April 27, 2008 at 5:47 pm |
More colors will correspond to the case of error-correcting codes in alphabets other than binary. Specifically, there will be a perfect strategy for
hat colors if and only if there is a perfect 1-error-correcting code on the alphabet with 
letters. Unfortunately, I don’t know much about codes other than binary ones.
Wikipedia is an uncharacteristically poor reference for this sort of thing, since the ECC articles are principly written by computer scientists, who seem to think that there are more important properties of error correcting codes than as sphere-packing problems in high-dimensions over finite fields.
April 27, 2008 at 9:52 pm |
Dear Greg,
I was asking this because the case with more colors actually seams radically more difficult: in facts, in the 2-colors case, there is one bad case (with mistakes) with many near good cases (where one prisoner correctly writes his color).
With more than 2 colors (k, say), instead, for every case where a prisoner correctly speaks, there are k-1 cases where he would say the wrong color, and these bad cases have Hamming distance 1 (and they are not the ‘isulated’ elements of a code).
Maybe, the problem can still be related to error correcting codes, but i was unable to see how to do this.
April 28, 2008 at 12:11 pm |
Oh, you are right… people don’t know how to guess if they are guessing ‘the opposite’ of the codeword. In light of this, I would suspect it is hard, if not impossible, to make error correcting code stuff work. This is a problem that happens with most other ways of generalizing this… it makes it seem like this particular solution to the hat guessing problem is more of a coincidence than anything else.
January 4, 2009 at 3:24 am |
[…] the way, Sune reminded us that Hamming codes also came up in a post by Greg Muller over at The Everything Seminar, who used the existence of a Hamming code in every […]
January 21, 2009 at 5:51 pm |
Also looks like a form of a “zero knowledge proof”l.
January 22, 2009 at 1:05 am |
pfft.. I was way off.. I thought for sure that Timmy would have 3 apples and Jill would have 4.
January 22, 2009 at 6:22 am |
If you can already agree on stuff beforehand why not just pass n times where n is the binary encoding of the hats you see?
June 4, 2009 at 2:49 am |
wow, it’s amazing how different my reasoning process was from yours. i also have a more direct solution for your hard case, if my solution is correct:
my reasoning cheats a little bit because i took into account the probabilities that you gave away. i did both parts in my head.
for your easy case, i basically sifted through all 8 permutations. the two “extreme” permutations immediately stand out (000 and 111; turning it into binary was immediate). the specialness of those two sequences jibes with the 75% probability. i then tried to see what was special about all the other sequences. it eventually occurred to me that all of them have at least one “odd man out.” i verified that. then that more or less led to the solution: if you see two hats of the same color, then assume that you are the “odd man out.” if you see two hats of a different color, then pass so as to minimize the number of wrong guesses.
the hard case i definitely thought about for much longer. but i think i have a fairly simple solution. it occurred to me that ecc codes are related, but i didn’t explicitly resort to them:
again, i cheated a bit by taking into account the probability you gave, i really thought you had maybe given a typo. again, i tried to see what was special about the two extreme sequences. i was kinda working with 8 bits in my head, so i was considering 00000000 and 11111111. after a long while and various detours, it finally occurred to me that for every sequence except 00000000 there is at least one ‘1’ in the sequence. this immediately points to there being a “least ‘1’” – assuming we can assign an index / ordering to every participant, then there is a least index with a white hat. this led me to the following solution:
Basically arrange it so that the person who is the “least ‘1’” guesses white:
– forget about the fact that you’re in a circle, just assume the linear ordering of participants numbered from 1 to n
– everyone looks to their right
– if anyone to your right has a white hat, then pass because you are not the “least ‘1’”
– if you don’t see anyone with a white hat to your right then guess white because you are probably the “least ‘1’”
– UNLESS you are in position 1, in which case you don’t have anyone to your right. in that case, look at everyone else. if everyone else is a zero, then arbitrarily guess white. everyone else is going to pass, so you certainly can’t pass because then you’ve guaranteed the loss. your guess wins for the sequence “00000001” but loses for the all-0 sequence.
the all-0 sequence is the only losing sequence, giving the 2^n – 1 wins.
apologies if i am making some glaringly stupid error here or misunderstanding the problem in some way.
June 4, 2009 at 10:42 am |
That’s a good way of thinking of the 3 person solution. However, thats not the optimal solution in the 8 person case… and actually, the eight person case is probably very hard.
When I said the optimal solution was
out of 
, I meant when there are 
players. So, for instance, the case 
says that for 
players, the optimal solution has success rate 
. My explanation doesn’t say anything about cases when there are a number of players other than a power of two minus 1.
Your approach correctly guesses sequences that end in
and the almost-all-zeros with a 1 at the end sequence, but I think it fails on all the others. To see this, note that if the right-most number is a 1, everyone except the right-most guy will pass. However, the right-most guy will also pass, unless all the other hats are black. Now, consider the case when the sequence ends with 
. The second-to-rightmost guy sees only a black hat (a zero) to his right, so he guesses white (1), and is wrong. Therefore, the only sequence it wins on are 
and 
.
Its actually rather hard to come up with a verbal strategy even in the 7 person optimal solution. It quickly becomes much easier to memorize a list of codewords and just check against it. For example, the codewords in the 7 player case are:
I would advise against trying to contemplate this set of numbers to see what the pattern is. Instead, the explanation at (7,4) Hamming code is quite good.
June 4, 2009 at 4:44 pm |
ugh, shoot, right
June 18, 2009 at 9:17 pm |
Hmmm… For the n person, k color case, you can win with probability at least (1 – (1-1/k)^n)/2 using a simple strategy.
Before the game starts, decide on a favorite color (Red) and figure out whether there’s a greater probability of an odd number of reds or a greater probability of a non-zero even number of reds. Since
P(Odd number of reds) + P(non-zero even number of reds) + P(No reds) = 1 and P(No reds) = (1-1/k)^n, we know that one of these choices is at least (1 – (1-1/k)^n)/2 .
Once you have that you’re ready to play. Suppose the greater probability was an odd number of reds. Then if you see an even number of reds, say “red”. If you see an odd number of reds, say “pass”. This wins exactly when there’s an odd number.
Are there other short strategies with nicer probabilities?
June 19, 2009 at 8:50 pm |
Oh, thats a fun solution. I don’t have any other quick ones lying around, but its worth noting that your general strategy of picking a ‘favorite color’ and then sort of ignoring all the other colors allows you to (imperfectly) adapt some nice solutions to the 2-color game.
So, for instance, if everyone has memorized the perfect solution for 2-colors and 7 people (not the easiest thing in the world to do), then for many colors and 7 people, they should simply treat hats as either ‘red’ or ‘not red’. The only problem is that if the optimal solution tries to force someone to guess ‘not red’, they will have to guess one of the non-red colors more-or-less at random. This means that this method is at worst half as efficient as the previous method, but a more reasonable estimate is that it is
times as effective (k the number of colors). Still, for groups that have 
people, this means they can always get it right at least 
of the time.
Its also interesting how both of our solutions tend towards
in various extremes. I wonder if there is some significance to this, or if it is just an artifact of our red/not-red approach. Probably the latter…
January 11, 2010 at 1:46 am |
Define a “guessing strategy” as a mapping from the number of black hats you see to corresponding action you take (guess white, guess black, or pass). Suppose every person must follow the same guessing strategy. Then the following guessing strategy is optimal for 4 through 8 people: Count the number of black hats you see (mod 3). If the result is 0, guess that your hat is white. If it is 1, guess black. If it is 2, pass.
With 4 hats, the group wins with probability 11/16; with 5, 22/32; with 6, 42/64; with 7, 85/128; and with 8, 170/256.
Using a computer, I have verified the above by evaluating each of the 3^n possible guessing strategies against all 2^n hat arrangements (where n is the number of people).
January 11, 2010 at 11:27 am |
Josh,
, and so by the above Hamming Code argument, the Hamming Code strategy works 
of the time.
Its an interesting strategy, and much better than most ‘randomish’ strategies. However,
May 3, 2011 at 8:28 am |
There is a strategy to win with probability 3/4 if there are from 3 to 6 people, probability 7/8 if there are from 7 to 14 people, probability 15/16 if there are from 15 to 30 people and so on. The strategy is that only 3 people answer (for example, the first three) when there are between 3 and 6 people, only 7 people answer when there are between 7 and 14 people and so on, using the Hamming Code argument. My question is: is there a better strategy for any number of people?
November 5, 2011 at 11:45 am |
ИБиз Македонија, Форум наменет за интернет бизнис и интернет маркетинг, black/white hat seo трикови. Дознајте како да успеете и да заработите, SEO совети и трикови….
[…]Hat Guessing Puzzles, The Revenge « The Everything Seminar[…]…
January 6, 2012 at 7:23 pm |
Very interesting 🙂
For 3 people, couldn’t they always win by guessing the colour of the hat of the person to their right?
January 6, 2012 at 7:49 pm |
In fact, if there are two colours, then they can guarantee a win for odd n and have a (2^n – 2)/2^n chance of winning for even n by using the same strategy. Just pick some arbitrary order for themselves before-hand and guess that their hat is the same colour as that of their successor. (With the successor of the last person being the first person)
January 6, 2012 at 7:53 pm
The point being that some sequence where no two consecutive people have the same colour hat must be one that alternates between black and white. For odd n, the last person will then have the some colour hat as the first. For even n there are two failing sequences: One for each possible colour of the first person’s hat.
🙂
January 6, 2012 at 8:49 pm
Ah, for even n >= 4, they could just “exclude” someone and then follow the odd strategy 🙂
i.e. There’s someone who doesn’t appear anywhere in the ordering. He can pass or guess arbitrarily or whatever.
For n = 2, I can’t se a way to get odds better than 3/4.
To achieve 3/4, just have both people gueess the same colour 🙂
For n = 1, you obviously can’t do beter than random guessing.
And for n >= 3, you can gurantee a win 😀
January 7, 2012 at 3:23 am |
Nevermind. Somehow forgot the provisio “no one guesses incorreectly”
Sue me, it was early in the morning and coldn’t sleep.
March 26, 2012 at 8:52 pm |
Alissia…
[…]Hat Guessing Puzzles, The Revenge « The Everything Seminar[…]…
August 30, 2013 at 10:01 pm |
whoah this weblog is magnificent i love studying your posts.
Stay up the good work! You recognize, a lot
of people are hunting around for this information, you can
aid them greatly.
July 28, 2014 at 5:44 am |
How can I be informed every time a brand new post has been prepared?
Love this page!
December 3, 2018 at 3:42 am |
We like your website, it has interesting information, Thank you!
March 26, 2021 at 12:49 pm |
fuck you
March 26, 2021 at 12:59 pm |
mother fucker