100 FogCreek Programmers (Feb 18,2001)
The solution posted is somewhat inadequate.
what if the arrangement is as follows
100 99 98 97 96..........................1
B B B R R ..........................50 Red and 45 Blue
the 100th man sees 52 (even number) Red hats, says Red and ends up getting shot. The 99th guy will also see 52 Red hats say red and get shot. Same is the case with the 98th person.
If on the other hand the 99 person hears the 100 person say red but get shot he knows the 100th person saw an even number but guessed wrong , so he can save himself by saying Blue. But this will only confuse the 98th person, because he thinks the previous guy saw and odd # of hats and said blue. Now he sees an even number of red hats, so he'll say Red and end up getting shot.
Whats a better solution ?
Have I mis-interpreted the solution suggested. Can anyone please help.
A person interviewing with MS very soon
Sunday, November 10, 2002
Yes you have misinterpreted the solution.
the point is that it is only the 100th guy that says "red" for an even number and "blue" for an odd number. Everybody else says the color of the hat on his head, which he can work out from the answers before.
So guy 99 sees an even number of hats in front of him just as number 100 does and says "blue", because if he had a red hat the number in front of him would be odd. Number 98 sees and even number in front and thus knows that his hat must be blue because if it was red number 100 would have seen an odd number, and thus says "blue". Number 97 in your example sees an odd number in front of him, and thus knows he must have the red hat that made 100 see an even number, so therefore says "red". Number 96 will now see an even number of red hats in front of him, but know that the total number of red hats must be odd because it is the even mumber that 100 saw minus the red hat on number 97. He therfore knows he has a red hat and says "red".
This works all the way down the line.
Thursday, November 14, 2002
Fog Creek Home