Puzzle : The best solution to the black and white hat puzzle

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 N-log_2 N correct guesses while he proposed an even simpler solution with N-1 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

Advertisements

Tags:

3 Responses to “Puzzle : The best solution to the black and white hat puzzle”

  1. Akshay Bapat Says:

    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.

  2. Akshay Bapat Says:

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

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: