Of Information and Puzzlement

A couple of days ago, I came across this very interesting puzzle. What is more interesting about this puzzle than the usual ways in which all puzzles of this kind are interesting, is the information theoretical aspect of the solution, or a way in which the problem may be perceived. Information theory deals with quantification of information, and gives us those limits beyond which we cannot compress data any further. It is obviously of great relevance to all communication systems and computation paradigms.

First the puzzle -

A king decided to play a game. There are a bunch of 100 people, who are to be lined up and then a colored hat (Blue or White) is to be placed on their heads. Now the really sardonic king decided that he will walk up to the person at the back end of the line (who can see the other 99 in front of him) and ask him the color of his hat. This he would do for everyone. If a person answered wrongly, he would be silently killed, else he would be silently allowed to escape (those standing in front of him will not know if he answered correctly or not). What is the maximum number people that can be guaranteed to be saved if they evolve some strategy for this ?(the game is explained to them beforehand, and we can assume them to be sufficiently intelligent, self-less and whatever else you may want them to be)

Consider the obvious solution. Every alternate person yells out the color of the hat worn by the person immediately in front of him. That person, of course gets to live. In this manner at least 50 can be saved. But one gets the feeling that this can be improved upon. The interesting part starts here. Consider the sequence of 100 hats to be an ordered sequence of bits. It is clear that all 100 cannot be saved. Now, suppose I tell you that the answer is 99 (which is the case, as we shall shortly observe). Doesnt it sound absurd? Does this imply that through the answer of the first person (1 bit) only, 99 people are able to figure out their hat colors? Can the information of 99 bits be conveyed/compressed into a single one !? Admittedly, this perplexed me and my friend for a small second. From an Information Theoretical perspective this seems too wierd to be true. But then this statement is not correct after all. What took us some time to figure out was that the answers of K persons should contain sufficient information for the (K+1)th person to figure out his hat color. This seems logically sound, and the solution to our puzzle of the 100 wise men is as follows:

Let the man at the back count the number of White hats he can see, and shout out "Blue" if they are ODD in number, and "White" if they are EVEN in number. The person immediately in front of him will count the number of White hats 'he' can see, and based upon the first guys answer, he will know his hat color (how?). Subsequent people will know that the second guy onwards are correct in their response, and hence they will be able to figure out the color of their hats as well. In this intelligent manner they can save at least 99 amongst themselves.

Now this puzzle is probably like many others you have seen, but the bit sequence analogy aroused enough interest in me to write a post on it !! The whole idea of discussing this problem started when a couple of friends of mine (V1 and V2) were giving an interview (with a high paying oil company) for a lucrative summer internship. Incidentally they answered wrongly, and so did I and so did my other friend(P1) when they asked us the following question....

"There is a cold drink vending machine, with three buttons COKE, SPRITE and COKE/SPRITE. The COKE/SPRITE button can dispense either of the two drinks with equal probability. You are told that the labels are mismatched. What is the minimum number of coins you require to correctly label the buttons of the machine?"

PS : Read the question carefully. For those who are interested, my friends who couldn't answer this question in the interview got selected (:P), and another one who did answer correctly (P2) wasn't !!

And I obviously cant end the post without celebrating Chelseas total annihilation by Manchester United last night !!
Cheers ...