[CrackMonkey] A cool problem

[Joey Hess]

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. 

(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 (??)

-- 
see shy jo