Hat Guessing Puzzles, The Revenge

by

    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 2^n-1, where the best win rate is 2^n-1 out of 2^n.  How is this possible?  (Answer below the fold)

    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, n of them?  Well, we need a strategy where the wrong guesses are concentrated and the right guesses are spread out.  Let’s make this a little bit more mathematical, by turning white hats into 1s and black hats into 0s.  Now, a possible hat scenario is a sequence of n binary digits, and every sequence is equally likely.

    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 0000000 is one of the agreed upon wrong sequences (this is for n=7).  Then, if someone looks around and sees all zeros/black hats, they will guess white.  That way, everyone will be wrong if it is all black hats; but if there is exactly one white hat, everyone wins!  Since it is n times more likely for there to be exactly one white hat than no white hats, this seems to work pretty well. 

    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 011, I instead send you 011011011 (we always agree on what code we are using ahead of time).  Now, if one digit gets flipped, you will see two of the three copies of the sequence agreeing and one differing, and you will know what I was trying to say.  However, this is a wildly inefficient code, since it takes three times as long to say anything.

    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 2^n-1, there is a ‘perfect code’ called the Hamming code, which will give us a choice of wrong sequences such that every possibility is either 1) a wrong sequence, or 2) exactly 1 digit away from a wrong sequence.  Hence, this is best possible strategy for hat guessing.  I am not going into the details of the Hamming codes, since the important thing here is that they exist. 

    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.

Advertisements

Tags: ,

27 Responses to “Hat Guessing Puzzles, The Revenge”

  1. John Armstrong Says:

    Now that’s really nice. I’ve seen this hat problem, but not the connection to ECCs.

  2. Jonathan Vos Post Says:

    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

  3. Maurizio Says:

    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!

  4. Greg Muller Says:

    More colors will correspond to the case of error-correcting codes in alphabets other than binary. Specifically, there will be a perfect strategy for n hat colors if and only if there is a perfect 1-error-correcting code on the alphabet with n 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.

  5. Maurizio Says:

    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.

  6. Greg Muller Says:

    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.

  7. Solution to POW-12: A graph coloring problem « Todd and Vishal’s blog Says:

    […] 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 […]

  8. Jeff Says:

    Also looks like a form of a “zero knowledge proof”l.

  9. Someone Says:

    pfft.. I was way off.. I thought for sure that Timmy would have 3 apples and Jill would have 4.

  10. Xianhang Zhang Says:

    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?

  11. thom Says:

    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.

  12. Greg Muller Says:

    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 2^n-1 out of 2^n, I meant when there are 2^n-1 players. So, for instance, the case n=3 says that for 7 players, the optimal solution has success rate 7/8. 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 10 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 00. 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 ...10 and \overline{0}1.

    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:
    0000000
    1110000
    1001100
    0111100
    0101010
    1011010
    1100110
    0010110
    1101001
    0011001
    0100101
    1010101
    1000011
    0110011
    0001111
    1111111

    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.

  13. thom Says:

    ugh, shoot, right

  14. Melanie Says:

    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?

  15. Greg Muller Says:

    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 \frac{1}{2} + \frac{1}{2k-2} times as effective (k the number of colors). Still, for groups that have 2^n-1 people, this means they can always get it right at least \frac{2^n-1}{2^{n+1}} of the time.

    Its also interesting how both of our solutions tend towards \frac{1}{2} 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…

  16. Josh Purinton Says:

    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).

  17. Greg Muller Says:

    Josh,
    Its an interesting strategy, and much better than most ‘randomish’ strategies. However, 7=2^3-1, and so by the above Hamming Code argument, the Hamming Code strategy works 7/8=112/128 of the time.

  18. Anonymous Says:

    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?

  19. ИБиз Македонија, Форум наменет за интернет бизнис и интернет маркетинг, black/white hat seo трикови. Дознајте како да успеете и да заработите, SEO сов Says:

    ИБиз Македонија, Форум наменет за интернет бизнис и интернет маркетинг, black/white hat seo трикови. Дознајте како да успеете и да заработите, SEO совети и трикови….

    […]Hat Guessing Puzzles, The Revenge « The Everything Seminar[…]…

  20. fingerpaint42 Says:

    Very interesting 🙂

    For 3 people, couldn’t they always win by guessing the colour of the hat of the person to their right?

    • fingerpaint42 Says:

      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)

      • fingerpaint42 Says:

        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.

        🙂

      • fingerpaint42 Says:

        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 😀

    • fingerpaint42 Says:

      Nevermind. Somehow forgot the provisio “no one guesses incorreectly”
      Sue me, it was early in the morning and coldn’t sleep.

  21. Alissia Says:

    Alissia…

    […]Hat Guessing Puzzles, The Revenge « The Everything Seminar[…]…

  22. New York City SEO Says:

    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.

  23. http://cecilialica.mywapblog.Com/50th-birthday-surprise-gathering.xhtml Says:

    How can I be informed every time a brand new post has been prepared?
    Love this page!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: