wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> SIMULTANEOUS HAT COLOR GUESSING
        
(Message started by: AlexH on Jul 29^th, 2002, 11:31pm)

Title: SIMULTANEOUS HAT COLOR GUESSING
Post by AlexH on Jul 29^th, 2002, 11:31pm

Interesting connection between these problems.

Given a group of N people, find the largest set H of hamming distance 3 on N bits (i.e. a 1-error-correcting code). Any player who sees that everyone else's hat matches one of the points p in H announces his hat as the opposite of the color it would be if P was correct. Any player who sees hats which require 1 change in addition to the determination of their own hat in order to be in H remains silent (passes).

Analysis:
If we land on a point Q which is adjacent to a point P in H, then the only player who will see the hats appear to line up with a point in H is the one whose hat is the difference between P and Q. He will correctly guess the opposite of his hats color in P and everyone else will remain silent. So, the players win. If we land on a point P in H, then everyone sees hats correspoding to P and all will incorrectly guess the opposite of their hat in P, so the players lose. Since there are N points adjacent to a point in H for every point that lies in H, this means that, of the space covered by H and the neighbors of P, our odds are (N/N+1).

If we exclude the "dead zone" of points not adjacent to points in H this result is optimal. For any win we must have one player say a color, and any player speaking has only a 50/50 chance of being correct since he has no information about his hat color. So the best we can do is have 1 player speak the correct color N/(N+1) of the time and have all players speak incorrectly the other 1/N+1 of the time.

For every length 2^m -1 there is a Hamming code which is perfect (i.e. the whole space is within 1 of a codeword) and so this solution is optimal for those lengths. For lengths between those values we have a lower bound on our success rate. We can always achieve at least as high a success rate on any N as we did on any M < N. Simply instruct the last N-M players to always remain silent and have the others use teh method for length M.

Alternately we could use the parity check section of the next higher Hamming code. For M between successive perfect Hamming lengths L(m) and L(m+1), this method will cover (M+1)/(L(m+1) + 1) of the space and have a M/(M+1) success ratio on that fraction. This method by itself will never be better than the lower bound stated above, however we may be able to tweak this situation to get at least some chance in the dead space outside of the neighborhoods of our codewords. If we wind up in the dead space then everyone will either remain silent or will know that we're in the dead space and can implement a fallback. I don't have any particularly good ideas about doing this and I'm not sure if we can actually beat the original lower bound with this method.

Finally, I'm no expert on coding theory so there may well be a better coding on the lengths between Hamming codes that I just don't know, if so, and if it can beat the lower bound above, then use that. :)

For the special case of size 3 we get the strategy of "if you see two hats of the same color, guess the opposite of what you see". We get a 3/4 chance of success which is optimal since 3 is a Hamming code length so our H is perfect.

Title: Re: SIMULTANEOUS HAT COLOR GUESSING
Post by Eric Yeh on Aug 1^st, 2002, 3:48pm

Yup. Nice job.

Title: Re: SIMULTANEOUS HAT COLOR GUESSING
Post by HyberZoid on Aug 4^th, 2002, 8:26am

First of all i see no connection between the problems other than the binary "values".

The group shares a hypothetical $3 million prize if at least one player guesses correctly and no players guess incorrectly.

This means that all the players who choose to guess (ie not to pass) must guess correctly, with at least one player guessing. The greatest chance then lies in choosing only one player to guess and the rest pass. Giving a 50/50 chance of winning.

The color of each hat is determined by a coin toss, with the outcome of one coin toss having no effect on the others. Each person can see the other players' hats but not his own.

This basically states that each player has no information about their own hat, which means their guess will be 50/50. If more than 1 player guesses (say n players) then the probability of winning is (1/2)^n.

AlexH said "if you see two hats of the same color, guess the opposite of what you see".

AlexH, you seem to be implying that the color of the other players' hats has some impact on the color of your own. The problem specifically states that the color of each hat is independant.

So basically, pick one person who gets a 50/50 guess (the rest pass).

HZ.

Title: Re: SIMULTANEOUS HAT COLOR GUESSING
Post by AlexH on Aug 4^th, 2002, 10:16am

You're assuming that the players' guesses are independent of the hat colors they see. The trick here is to use the hat colors that the players see to ensure that when a player guesses right, he guesses right alone, but when he guesses wrong, everyone guesses wrong along with him. Each time someone guesses they have only a 50/50 chance of being right, but all of the "wrong 50 percents" are piled on top of each other while the "right 50 percents" are alone and cause a win. Take a look at the concrete case where n=3 and we use the strategy I describe and you should see that the odds of success are 75 percent making this better than the "1 person guesses" strategy.

Title: Re: SIMULTANEOUS HAT COLOR GUESSING
Post by kenny on Aug 5^th, 2002, 1:41pm

The correct answer has a probability of success of (2^n-1)/(2^n).

I'll post the solution in a separate thread.

Title: Re: SIMULTANEOUS HAT COLOR GUESSING
Post by kenny on Aug 5^th, 2002, 1:51pm

My bad.

I misread the puzzle. I thought that, if no one guessed at all, then the players would be given another chance. Apparently, if no one guesses, then they lose.

I guess my solution is for a slightly different puzzle.

-- Ken

Title: Re: SIMULTANEOUS HAT COLOR GUESSING
Post by AlexH on Aug 5^th, 2002, 6:16pm

If everyone remaining silent caused a replay then I think the best odds of success would be n/(n+1) and you'd achieve that using the same method as in the original problem. The chances would be exactly the same as the silence=loss case for the perfect hamming lengths of n=2^m - 1, but in between those lengths you'd gain an advantage. Basically allowing retrys on silence just be removes the need for the 1-error correcting code to fill the space. The explanation for n/(n+1) being optimal also applies to this new problem so I don't think that odds of (2^n - 1) / 2^n are possible.

Title: Re: SIMULTANEOUS HAT COLOR GUESSING
Post by Bazza on Dec 15^th, 2003, 8:05pm

Hats are black or white randomly, there is no option in the question not to answer, therefore Number 10 has to answer first and as he has no clues at all as to the colour of his hat he has to guess. He has a 50/50 chance of living, but since he can see all other hats he should state the colour of hat number 9. Number 9 will then definitely live (as the plan has been discussed beforehand and 9 will know what is going on). Start again with Number 8 who has to guess, but will state the colour of 7's hat, etc etc.. Therefore 1,3,5,7,9 will definitely live, and 2,4,6,8,10 have a 50/50 chance of living.

Title: Re: SIMULTANEOUS HAT COLOR GUESSING
Post by rmsgrey on Dec 16^th, 2003, 8:58am

a) you're talking about a (slightly) different riddle - try looking for a thread with a title like "single file hat execution" or similar

b) your answer isn't optimal - check the other thread(s) for details

Threads:
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027806438
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027917276

[e]removing duplication in thread list[/e]