Fog Creek Software
Discussion Board

soln to fog creek programmers

I doubt that the solution would work in some extreme scenario.

i.e. since it is not specified how many red or blue hats among 100, you may arbitrarily assign numbers to red and blue as long as the sum is 100.

OK, if the first two persons #1 #2 are wearing red hats and all the rest 98 are wearing blue hats.Then based on the stategy provided, #100~#3 person would say "red" although all of them have blue hats on head. Therefore, unfortunately all of them got executed. Then #2 would also be killed. Oops, only #1 could survive since there is only one person before #2 and he knows for sure which hat he is wearing. The solution gets stuck here.

The inherent drawback arises from 4 different cases.

Friday, February 8, 2002

You misunderstood the solution, I think...

#100 would say "red" because there are an even number (2) of red hats in front of him.  #99, however, would say "blue."  This because #100 said "red," meaning there are an even number, yet #99 still counts an even number of red hats.  Thus, since both he and #100 counted even, he must be wearing blue.  This same logic follows to the end.

Mike McNertney
Wednesday, February 20, 2002

*  Recent Topics

*  Fog Creek Home