[CrackMonkey] A cool problem

[Joey Hess]

Seth David Schoen wrote:
> 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?

They can guarentee that n/2 people are saved, as follows:

* The people number off from 1 .. n. 
* Every odd person says the color of the hat of the even person just following
  him (and dies). If he is the last person, he just guesses a color.
* Every even person repeats what the previous person said (and lives).

I think there are better solutions though. There are certianly better
solutions if you're a short person.

Of course, you should be aware that Mr. Bad is listening, and will shortly
be mailing you information about the colors of the hats of those shorter
than you. He knows where you live.

-- 
see shy jo