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 2^n, 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

Advertisements

Tags: , , ,

4 Responses to “Puzzle : Black and white hats revisited, .. yet again!”

  1. Pratik Poddar Says:

    I posted the second part in my blog a few days back. Solution too posted in comments!! πŸ™‚

    http://pratikpoddarcse.blogspot.com/2010/01/hats-in-circle.html

    Pratik

  2. Pratik Poddar Says:

    BTW, your solution is different and awesome πŸ™‚

  3. Puzzle : Coloured Hats and Wizards! « Me, Myself and Mathematics Says:

    […] post : here, here and […]

  4. Puzzle : Black and White hats! « Me, Myself and Mathematics Says:

    […] posts : here, here, here and […]

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: