Puzzle : Black and White hats

HI All,

So I am back again with a puzzle which I found here. Writing the problem statement down here for completeness.

Problem : 100 person are standing in a straight line all facing the head of the line. So the last person can see all 99 persons ahead of him, the second last person can see all 98 persons ahead of him. Some black and white hats are randomly distributed to these 100 persons. All the hats may be white or all the hats may be black or any other combination may be possible.

Starting from the person standing at last, you ask him/her to guess the colour of his/her own hat ( which obviously he/she can not see ). After you are done questioning everybody, you give a score to that team depending upon how many of them could guess correctly. So for example, out of 100, if 5 could guess colour of their hats correctly then the score would be 5.

Those 100 persons are given liberty to decide on a strategy before hats are put on their heads. What strategy should they decide in order to maximize their score in the worst case?

For example one strategy is for everyone to say “black”. If all the hat happens to be black ( which is the best case for this strategy ) then the score would be 100 but in the worst case ( when all the hats are white ) their score would be zero. The question is to improve the score for all possible cases ( irrespective of hat distribution ).

Another strategy could be that all even numbered person can call out colour of the hat of the person standing immediately next to him/her. Now all the odd numbered person can correctly guess colour of their hat. This strategy will give at least 50% accuracy ( “at least” because it is quite possible that odd-even pair might have the same colour ). So this strategy gives 50% worst case accuracy .

Devise a strategy to improve this accuracy.

I am writing the solution right ahead…so those who want to scratch their head for a while in order to come up with a solution may not read further.

Solution : Actually, I would not say this is the best possible solution. I should rather say that this is the best possible solution I can think of.

We need 7-bit to represent numbers upto 128. So last seven person standing in line will serve as a binary representation of a number ( black = ‘0’ and white = ‘1’ ). This number would tell how many total “black” hats are there on first 93 persons.

Say for example, if number is 53.

The person numbered 93 can now calculate total number of black hats on the 92 persons he/she can see. If the total is 53 then he would say “white”, if the total is 52 the he would say “black”. Please note that the total can only be 53 or 52 and no other number is possible. Now the person numbered 92 can again calculate number of “black” hats he sees and number of “black” he heard. Again if the total is less than 53 he would scream “black” else he would say “white”.

Needless to say, this strategy gives 93% accuracy irrespective of how the hats are distributed.
That was simple enough, eh?

–Saurabh Joshi

Tags: puzzle