[CrackMonkey] Think I figgered it out

[Mr. Bad]

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

--
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 Mr. Bad <mr.bad at pigdog.org> | http://pigdog.org/ |  RoR - Alucard
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~