[CrackMonkey] A cool problem

[Seth David Schoen]

Joey Hess writes:

> Mr. Bad wrote:
> > 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.
> 
> No they don't because the adversary has arranged for them to have a
> different color hat, since he knows this strategy is being used. The 50%
> "degenerate" case is guarenteed to happen. 

Yes, you're right, too, Joey.  The first person's comment can only be
determined by what he sees.  Nobody ever sees his hat, and, if his
comment is not wasted, it must be a deterministic function of what
he sees.  The adversary can then arrange for his hat to be the wrong
color so that he will be killed.

> (Of course, then elements of the prisoners dilemma enter the question -- do
> the odd people turn traitor and say the opposite of what they agreed to?)
> 
> > I was trying to think up a stream-encoding, based on the previous
> > responses. 
> 
> Me too. I have a start, but it immediatly becomes very complicated.
> Something like:
> 
> * The first person looks at all the visible hats and says the most common
>   color (MCC). (If it's half and half, do something I haven't figured out.)
> * The second person looks at all the hats, and considers the first person's
>   MCC. 
>   - If the hats he sees have a different MCC, then his hat must be the color
>     the first person said, since adding it to the set changes the MCC. So,
>     repeat that.
>   - If he sees half-and-half, then his hat must be what #1 said, since it
>     breaks the tie, so repeat that.
>   - If the hats he sees have the same MCC as what #1 said..
>     - but that MCC only leads by one hat, then adding his hat to the set
>       must not change the MCC, thus his hat is the MCC. Say it.
>     - but the MCC leads by more than 1 hat, then he can't know what color his
>       hat is. Indicate that by saying whatever color #1 did not say.
> * The third person considers both the past responses.
>   - If #1 and #2 agreed, then.. something complex I haven't figured out.
>   - If #1 and #2 disagreed, then #2 saw a MCC that was the same color as 
>     what #1 said, and that MCC led by more than 1 hat. So if the MCC #3 sees
>     leads by..
>     - 1 hat, then his hat must be the color #1 said, so say that.
>     - more than 1 hat, then he can't know what color his hat is. Indicate
>       that by (??)

I think there is an attack on the best version of this MCC thing that still
always makes it save fewer than n-1 people.

I was thinking that the statement of the problem should add that, if
anyone does anything other than immediately answer "Red" or "Blue",
_everyone_ would be killed.  (That prevents someone from, say, blurting
out "242", when that happens to be a binary encoding of the hat colors
of all the remaining people.)

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