Well,

Me and Deepanjan discussed the black and white hat puzzle when Deepanjan admitted about my solution being elegant and simple. His appraisal put a smug smile on my face when Chandan walked in. I described him the puzzle zealously as I was still being happy about my little feat. I described him my solution which is correct guesses while he proposed an even simpler solution with correct guesses. No wonder he is a doctorate student of Prof Manindra Agarwal.

**Solution :** The last person in the line takes XOR of the bit string in front of him ( with black=0 and white=1). 99th person now can check the parity of the first 98 persons with what the last person had said. From this he/she can easily make out whether his is bit ‘1’ or ‘0’. Others would follow the same strategy.

I guess I learned a lesson not to be so smug so soon about such things.

–Saurabh Joshi

### Like this:

Like Loading...

*Related*

Tags: puzzle

This entry was posted on May 12, 2008 at 12:57 pm and is filed under puzzle. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

January 17, 2011 at 5:57 am |

I think this is a similar solution, but instead of the exor, the last person could indicate “whether the number of black hats in front of him is odd or even” using black and white respectively.

So if he says “black” (which means there are odd number of black hats in front of him), if the 99th person would then count the hats in front of him. If he finds even number of black hats, he concludes that his hat is black (to make the total number odd) and white if he finds odd number of black hats in front of him.

The rest of the lot know what the 100th person said and also what each one at their back says and thus could follow the same odd/even method to conclude what color their hat is.

January 18, 2011 at 10:06 am |

Well,

and how do you calculate odd or even? Note that XOR is a parity function. So both answers are exactly the same.

January 22, 2011 at 6:37 pm |

Yeah, well exactly the same, you are right. I wasn’t sure about XOR when I first read this.