[bushindo]

Let's say that you and 27 other prisoners are on a death row. The warden gives you and your fellow prisoners a chance to win your freedom through a game. The game is as follows,

1) When the game starts, the warden will blindfold all 28 prisoners and arrange them in a circle.

2) The warden will put on each prisoner's head either a RED, BLACK, or WHITE hat. The warden will choose the color for each prisoner uniformly by tossing a fair die.

3) The warden will then remove the blindfolds. Every prisoner will be able to see the hats on the other 27. Each person will not know the color of his own hat.

4) The warden then gives everybody 1 minute so that each person can think about what his hat color is. At the end of that 1 minute, the warden will provide each prisoner with some paper, and all 28 prisoners must write their hat color at the same time. If 4 or less people got their hat colors correct, then everybody win their freedom. Otherwise, they all go back on the death row.

5) Each person is absolutely not allowed to communicate with his fellow prisoners during the game by speaking, facial expressions, body language, etc. The warden reserves the right to cancel the game and put everybody back on the death row if he see these types of behavior.

You and your 27 friends have 1 night to discuss a strategy. Find a strategy that makes your chances of freedom as high as possible.

EDIT: fixed a wording mistake that was pointed out by smoth333

[Molly Mae]

Yeah, I guess I was looking for a 100% win chance for 4 or fewer correct.

Quick query: Are the prisoners allowed to rearrange themselves (based on their own observations) after the blindfolds have been removed? I assume no, since that would also lead to a >99% winning strategy.

[Molly Mae]

For 7, choosing the greatest number of hats seen wins more than loses, so we'll start there. For any distribution of hats where the greatest number of any given colour is <4, four people are assured to guess the wrong colour (or the right colour, depending on your perspective). The other three have each an independent 2/3 chance of guessing the wrong colour. 4-3-0 distributions have a chance at working, but aren't optimal. I'm working on all distributions now.

[araver]

... and reconsidering my n=3 case above, but with a different function than the one I posted before ( as f(x,x)=x f(x,y)=z is hard to generalize .. guess it was a remnant from one of my Mistery Ops), I believe there was a very quick general function all along.

Assume white=0, black =1, red = 2 (or something of the sorts, what's important is that all agree beforehand on the same conversion table):

f_n(x₁,x₂, ... x_n-1) = [2 - (x₁+x₂ + ... x_n-1) ] mod 3

or in other words (the above was just more of a quick feel of the new editor):

Add all the other hat numbers and guess the complement modulo 3.

Using the above function one guesses correctly his own hat color only if and only if the sum of all hats equals 2 modulo 3.

But when that happens, all of them guess correctly simultaneously (which I guess is easier to see with this function than it would for any other separation code I can think of).

Given the 3^n possible cases (uniform distribution), it is fairly easy to see that there are 1/3 chances of the sum of all hats to equal 2 modulo 3, leading to the (maximum?) 2/3 chances of all being incorrect at the same time ("synchronized out of phase" ).

Was this what you had in mind?

Edited August 26, 2011 by araver

[bushindo]

... and reconsidering my n=3 case above, but with a different function than the one I posted before ( as f(x,x)=x f(x,y)=z is hard to generalize .. guess it was a remnant from one of my Mistery Ops), I believe there was a very quick general function all along.

Assume white=0, black =1, red = 2 (or something of the sorts, what's important is that all agree beforehand on the same conversion table):

f_n(x₁,x₂, ... x_n-1) = [2 - (x₁+x₂ + ... x_n-1) ] mod 3

or in other words (the above was just more of a quick feel of the new editor):

Add all the other hat numbers and guess the complement modulo 3.

Using the above function one guesses correctly his own hat color only if and only if the sum of all hats equals 2 modulo 3.

But when that happens, all of them guess correctly simultaneously (which I guess is easier to see with this function than it would for any other separation code I can think of).

Given the 3^n possible cases (uniform distribution), it is fairly easy to see that there are 1/3 chances of the sum of all hats to equal 2 modulo 3, leading to the (maximum?) 2/3 chances of all being incorrect at the same time ("synchronized out of phase" ).

Was this what you had in mind?

Yup, perfect solution. It's nice to see you around this New Puzzles forum once more. Reminds me of the grand old time when we solved 'Team of 15' together. Good old times =)