[CrackMonkey] Re: A cool problem

[David Cassel]

This *is* a cool problem.  The parity solution seems like the best answer
so far.  

Here's a couple of interesting alternate solutions that give a survival
rate higher than 50%.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

This is a variation on saying the color of the person in front of you.

If the first person announces the color of the hat on the *last* person in
the row (as their own guess), and the second person announces the color of
the hat on the second-to-last person (as their guess), then everybody in
the second half of the line will know exactly what color they're wearing.

That would mean that you'd get a guaranteed 100% survival rate for the
second half of the line and a 50% chance of randomly guessing right for
the first half.  Except that since the adversary has announced they're
going to dispense the hats to maximize the killing, they could guarantee
that *everybody* in the first half of the line is wearing the wrong color
hat.  (Though at least you've got a *guaranteed* 50% survival rate and not
the *probable* 50% survival rate you'd get from guessing randomly.)

But there's a way around it with a slightly-different plan.  The first
person promises to announce either the color of the last hat in the line,
or the *opposite* of the color of the last hat in line -- and then
everyone else in the first half of the line will also do the same thing.  
(They'll know which to do by comparing the color of that last hat to what
the first person guessed.)  By not saying which one they're going to do in
advance, the adversaries won't be able to screw the first half of the
line. Survival is guaranteed for the second half, and the adversaries
either do an all-or-nothing arrangement on the first half of the line, or
arrange the hats so that exactly 50% of the guesses will result in death.  
The adversaries can guarantee a 25% death rate, or gamble on either 50% or
0%. (FWIW, the "average" survival rate after several runs of this would be
75%.)

It kind of depends on how, exactly, the adversaries are going to behave.
Otherwise you could say loudly, "We'll just all guess RED!  That way half
of our guesses are guaranteed to be right."  Since the adversary has sworn
to kill the maximum number of people, they'll put everyone in blue hats.

Then everyone guesses blue, and they all go free.  100% survival rate. (If
everyone is smart enough to figure out what's going on!  And if the
adversary is dum enough not to realize that seeing everyone in front of
you in a blue hat is a dead give-away...!)

This is the best solution I came up with:  An 82.5% survival rate.

It's a variation on someone else's plan...

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
The first person -- and every third person after them -- makes the
following vow.  "If the two hats in front of me are the same color, I'll
guess red.  If they're not, I'll guess blue." 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

It's a little complicated, but it starts when the very first person in
line -- a sacrificial person, not part of the groups of three -- says "The
color I guess will be the 'signal' color for 'the two hats in front of me
are the same color' for everybody in line after me."  Then the adversaries
won't know in advance what hat to put on the remaining people in line.  
(Specifically, the people who are standing *before* the pairs of two that
are going to be saved by the statement of one of the signal colors.)  Get
it?

---
"This is the font of wicker my friend.  
 It is assembled downstream by an army of gnomes."

	-- Pokey the Penguin