Fog Creek Software
Discussion Board

fog creek programmers


The explanation (answer) is too long. Probably we need to turn "red" to be 1 and "blue" - 0, then the #100 programmer can see and say the XOR of other 99 guys.
After that, any guy number i can see XOR of all in front and make a conclusion about himself which based on total XOR and the previous answers. So, all, exept #100, can be saved. Am I wrong?

Saturday, January 1, 2005

Yes, that's a good answer but it doesn't take so long to explain.

The first guy says red if there are an even number of red hats in front of him, and blue if there are an odd number.  The guy in front of him knows how many red hats are in front of him which tells him (and everybody else) what color his hat is.  And so on.

So 99 of them are saved and the 100th has a 50:50 chance.

As long as none of them make a mistake they're all set.  But if one of them miscounts the number in front of him, or miscounts the number that have already been announced, he could throw it off for everybody in front of him too.

I misread the question, and thought each was guaranteed only that he could see the hat in front of him.  Then the even ones should say the color of the hat they see, and the odd ones should say the same thing.  The odd ones will all be saved along with a random half of the even ones.

J Thomas
Sunday, January 2, 2005

i dont think thats correct answer,
lets take one case - if all the people are having red hat
100th person will tell blue 99 person red and then what...
all people are having red hat when u proceed further the number of red hats will become odd and even alternatively but each person has to say red (if they have to survive).

can any body pls explain the answer

surya prakash
Wednesday, January 19, 2005

i think you all made it too difficult. if the programmer BEHIND always said the color of the hat AHEAD, the first gal has a 50% chance of being correct, but everybody else is TOLD which color they have on.

same result, though.

Saturday, January 22, 2005

^^You beat me too it. Are we missing something that would make this not work. If not, then it seems like the obvious answer that everyone should come up with.

Saturday, February 26, 2005

Ok. I see our error. Each prisoner would have to be able to guess his/her color and then tell the person in front his/her color. Since he can only say on thing, this won't work.

Sunday, February 27, 2005

*  Recent Topics

*  Fog Creek Home