[CrackMonkey] A cool problem

[Seth David Schoen]

... posed by my girlfriend, who heard it from some grad student friends at
Berkeley:

n people are captured by an adversary and told that, after this scenario
has been explained to them, they may mutally agree on a strategy (with the
adversary listening to all their discussions) and then use it to try to
save as many people as possible.

The people will be lined up in a row, sorted by height, so that the first
person can see everyone else, the second person can see everyone else but
the first person, the third person can see everyone else but the first
and second people, etc.

Each person will be wearing either a red or blue hat and (of course!)
cannot see what color hat he or she is wearing.

The people will be asked, one after another, in the order they were lined
up, "What color hat are you wearing?"  (The first person is asked, and
answers; then the second person is asked, and answers; then the third
person is asked, and answers, and so on.)

Each person must answer promptly (no manipulation of latency allowed).
Each person must say either "red" or "blue", and may not say anything
else at any time.  Nobody is allowed to decline to answer.

Once everyone has answered, everyone who answered correctly is released
and everyone who answered incorrectly is killed.

The people are also told that, after they have conferred on their
strategy, the adversary will choose their respective hat colors so as to
maximize the number of people who will be killed, given what can be deduced
from what they have said about their strategy.  (This is to say that their
hat colors will be chosen adversarially with respect to their strategy.)

Now the people are allowed to deliberate about their strategy, knowing
that their deliberations are overheard.

By guessing randomly, they could obviously save everyone with probability
1/(2^n), but they would expect to save only n/2 people, and they would
not be guaranteed to save anyone.

That doesn't sound like a great idea.  A better strategy would guarantee
that some number of people would be saved.

How many people can they definitely save?  How?  How many people can they
possibly save that way?

-- 
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