Puzzle : Black and white hats revisited, .. yet again!

The credit for this puzzle again goes to ramprasad. And I think that for coming days he will add a lot to my knowledge and blog as he got hold of peter winkler’s book on puzzles.

As usual, there are n people ( finite this time ). Black and White hats are randomly placed on each of them. They have to give their answer simultaneously and they have no means of communicating with anybody else.

1) In this puzzle, every one must guess the color of their hat. Come up with a strategy so that every one guesses the color correctly with probability 1/2 ( and I think this is the best you can achieve ).

2) In this variation, people are allowed to guess or say “pass” ( basically saying they do not want to guess ). Group of people will succeed if there is at least one person who has guessed the color of his/her hat correctly, and none of the persons guesses it wrong. What is the strategy to follow so that you can maximize the probability of success??

Solution :

1) I could get the solution of this problem after a bit of pondering. Let ‘1’ stand for black and ‘0’ stand for white. Everybody will assume that the summation of the entire string is 0 mod 2. So a person sums up from all the hat he/she sees and then choose the color so as to make the grand total 0 mod 2. Given any random strings from , the probability that the total of the string is 0 mod 2 is 1/2.

2) Two is a bit tricky and I could not get it. Let us try for n=3. The strategy would be that if a person sees the same color on the other two, then he guesses the opposite color otherwise he will pass. It is easy to see that they will fail only when the string is 000 or 111. Probability of suceess is 3/4.

In general, for n people, they can come up with some “Perfect Code” ( Just google it, will ya? ). Code with hamming distance 3 and error correcting capability of 1 bit. Now, a person sees the remaining part of the string, if by guessing ‘0’ the string falls into the code, he/she will guess ‘1’ and vice versa. Otherwise, the person will pass. One can see that the experiment will fail when the assigned string is one of the string in the code. In all other cases, the person, flipping whose bit makes the string fall into the code, guesses it right and rest all will pass. But then there are n times more strings, which are hamming distance one away from code. So the probability of failure would be O(1/n).

Sorry for the shaddy explanation, but believe me, it works!

 

Related post : here and here

Tags: black and white hats, coding theory, math, puzzle