[CrackMonkey] A cool problem

[Mr. Bad]

>>>>> "JH" == Joey Hess <joey at kitenet.net> writes:

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

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

Ah, but there's a 50% chance that the odd person has the same color
hat as the even person immediately following him/her. So, if the odd
person says the color of the even person, they have a shot at being
saved, too.

On average, they'll actually save 75% of the people. However, the
question is "guaranteed" rather than "odds-on," which of course in the
degenerate case (where the bastardo math-loving savages, having heard
the strategy, alternate colors of every hat), gives the 50% you named.

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

I was trying to think up a stream-encoding, based on the previous
responses. 

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

Well, that's not a very well guaranteed mechanism.

~Mr. Bad

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