[CrackMonkey] Think I figgered it out

[Seth David Schoen]

Mr. Bad writes:

> Now that I think of it, I THINK you can save N - 1 people, using
> parity values.
> 
> Let's say that you assign 0 and 1 to red and blue, respectively. Then
> the first person can give a parity value to the entire rest of the
> group: blue if the sum is odd, and red if the sum is even.
> 
> Each person afterwards hears the responses of the people behind
> him. He can calculate the parity of those behind him from their
> responses. He can see the parity of hats in front of him. So then he
> knows 3 values: total parity, before parity, after parity. (Parity of
> a null group, like the "before" parity of the second person or the
> "after" parity of the last person, is 0).
> 
> If the TOTAL parity is odd, and the parity of the groups before and
> after him are the same, then he knows that he is a 1 (blue). If the
> total parity is odd, and the parity of the groups before and after him
> is different, he knows that he is a 0 (red).
> 
> Similarly, if the total parity is even, and the parity of the groups
> before and after him is different, he knows he is a 1 (blue). If the
> total parity is even, and the parity of the groups before and after
> him is the same, he must be a zero (red).
> 
> That oughtta do it.

Mr. Bad is completely correct in every detail.  Well done.

I was impressed with the ingenuity of several other answers.  OK, so the
other answers don't save n-1 people, but they were creative and
interesting.

-- 
Seth David Schoen <schoen at loyalty.org>  | And do not say, I will study when I
Temp.  http://www.loyalty.org/~schoen/  | have leisure; for perhaps you will
down:  http://www.loyalty.org/   (CAF)  | not have leisure.  -- Pirke Avot 2:5