[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

[Guest]

They should all guess the same color agreed upon the night before. I (likely)

may have done the math wrong but I think it is a 99.99% chance that you have at

least 4 of 27 with that color.

[Guest]

well there is 9 of each color. but i like the idea of every1 picking the same color.

[bushindo]

<p>

</p>

<p>

They should all guess the same color agreed upon the night before. I (likely)</p>

<p>may have done the math wrong but I think it is a 99.99% chance that you have at</p>

<p>least 4 of 27 with that color.

</p>

<p>

</p>

<p> </p>

<p>Actually, you are right about the winning chance. I made a mistake in phrasing this puzzle. The condition should have been 'If 4 or less people got their hat color correct, then everybody wins.' In the incorrectly quoted version, the ideal solution is pretty much as you say. I fixed the wording the the original post.</p>

[bushindo]

They should all guess the same color agreed upon the night before. I (likely)

may have done the math wrong but I think it is a 99.99% chance that you have at

least 4 of 27 with that color.

Actually, you are right about the winning chance. I made a mistake in phrasing this puzzle. The condition should have been 'If 4 or less people got their hat color correct, then everybody wins.' In the incorrectly quoted version, the ideal solution is pretty much as you say. I fixed the wording the the original post.

[Guest]

I haven't really got much of a clue for this one but i have some theory....

there are 28 of you in total

there are three different colours

the die is "fair"

if that is then true we could assume that 9 people will have a Black Hat, 9 people will have a Red Hat and 9 people will have a White Hat.

This only adds up to 27 but the remaining person could have any of the three possible colours.

If all the prisoners work to this logic, they would be able to see who has what colour and we would assume that more than four could guess correctly in order to gain freedom...

E.g. 8 Black 10 White 9 Red - Hat being worn is Black

9 Black 8 White 10 Red - Hat being worn is White

10 Black 9 White 8 Red - Hat being worn is Red

9 Black 9 White 9 Red - Hat being worn could be any of the three

I think this is right?

Or.....

They could just guess and hope for the best

[Guest]

Hmm, makes it a little more difficult that way! I will work on an answer with the new win condition.

[Guest]

Actually, you are right about the winning chance. I made a mistake in phrasing this puzzle. The condition should have been 'If 4 or less people got their hat color correct, then everybody wins.' In the incorrectly quoted version, the ideal solution is pretty much as you say. I fixed the wording the the original post.

This is confusing me now :L does it mean that if 1 or 2 or 3 or 4 people only, get their hat colour correct then they can leave? Meaning that if more than 4 people get their hat colour correct then they'd go back on the death row?

[bushindo]

This is confusing me now :L does it mean that if 1 or 2 or 3 or 4 people only, get their hat colour correct then they can leave? Meaning that if more than 4 people get their hat colour correct then they'd go back on the death row?

It is indeed as you say. If 0, 1, 2, 3, or 4 people got their color correctly, then everybody wins. Any more than that and they all go back to the death row.

[Guest]

I haven't really got much of a clue for this one but i have some theory....

there are 28 of you in total

there are three different colours

the die is "fair"

if that is then true we could assume that 9 people will have a Black Hat, 9 people will have a Red Hat and 9 people will have a White Hat.

This only adds up to 27 but the remaining person could have any of the three possible colours.

If all the prisoners work to this logic, they would be able to see who has what colour and we would assume that more than four could guess correctly in order to gain freedom...

E.g. 8 Black 10 White 9 Red - Hat being worn is Black

9 Black 8 White 10 Red - Hat being worn is White

10 Black 9 White 8 Red - Hat being worn is Red

9 Black 9 White 9 Red - Hat being worn could be any of the three

I think this is right?

Or.....

They could just guess and hope for the best

Going back to my first spoiler, I have another theory....

As I said in my first spoiler, there are four possible scenarios to determine the hat colour each prisoner is wearing. With this in mind, we know that there can only be a maximum of four people who can guess correctly. With these two points acknowledged, the prisoners can therefore discuss among them who will write down the correct hat colour and who will not - therefore, they should all plan to write down the incorrect colour of their hat.

If they agree to do this, only one person can write down the correct colour - this will be when the scenario is as follows - 9 Black 9 Red 9 White - Here he will have to guess the colour of his hat but whether he guesses correctly or not will not matter because he will be the only one who has guessed correctly meaning the requirements for freedom are met.

I hope this makes sense and I think it's right...?? :L

[Guest]

Have everyone guess that there Hat color is BLUE.

Zero answers should be correct which is less than 4.

[Guest]

They should all guess pink...

[Molly Mae]

@MidnightLove: I don't know that anyone can actually see what another person writes down. It breaks the communication rule.

I've divided the 28 people into four groups of seven and had each person write the colour he sees most prevalent in his own group--statistically each group should have a 3-2-2 distribution. 4/7 in this case would get us closer to our goal, while the other two each have a 2/3 chance to get theirs wrong. This strategy loses immediately if there are 6 of any colour in a single group, though. With 5 of any colour in a single group, every other group must get their hat colour wrong.

Almost certainly not optimal. I'll come back shortly after I give it a think.

[Guest]

@MidnightLove: I don't know that anyone can actually see what another person writes down. It breaks the communication rule.

I've divided the 28 people into four groups of seven and had each person write the colour he sees most prevalent in his own group--statistically each group should have a 3-2-2 distribution. 4/7 in this case would get us closer to our goal, while the other two each have a 2/3 chance to get theirs wrong. This strategy loses immediately if there are 6 of any colour in a single group, though. With 5 of any colour in a single group, every other group must get their hat colour wrong.

Almost certainly not optimal. I'll come back shortly after I give it a think.

They wouldn't need to look at each others bits of Paper Molly Mae.... I'm pretty sure I wrote it down clearly but maybe I didn't.... I'll have a look...

[Guest]

<p>

They should all guess green, there is no stipulation that their guess must be one of the colors visible.

</p>

[bushindo]

Have everyone guess that there Hat color is BLUE.

Zero answers should be correct which is less than 4.

*Sign*, the brainden never ceases to amaze me with the out-of-the-box solution. Congratulations, you win the out-of-the-box solution. There's still the intended in-the-box solution where each person can only write down Red, Black, or White. No one has that solved yet.

[bonanova]

I love this problem.

The closest approach to a procedure I can imagine is some variation

of the procedure for the binary [black hat, white hat] case where

exactly half must be right.

Assuming an even number of prisoners.

Assign each prisoner beforehand to group A or group B.

Pairs of prisoners [one from each group] will then guess as follows:

A will guess B's color; B will guess the opposite of A's color.

Each pair will produce exactly one correct answer!

[Guest]

Every prisoner should guess that his hat is the color of the person to his left. The likelihood that there are more than four hats of the same color next to each other is small. I'll let the mathematicians do the statistics...

Edited August 26, 2011 by deedub

[Guest]

The other idea that is more certain, but more likely to get shutdown by the warden is:

Each prisoner looks at the hat color of the person to his left.

(1) If it is "red", he writes he writes red immediately (Now, all the reds know to write "black" or "white")

(2) After counting to 10, if the person to the left is wearing a "black" hat, the individual writes "black" (Now, everyone should know what hat color he has

(3) Anyone left writes "red" or "black", because the must be wearing a white hat, because the person to their right has not written anything.

Everyone should try to write the wrong answer. This should almost certainly ensure that 4 or less will get it correct. However, it may be deemed a form of "communication".

Edited August 26, 2011 by deedub

[Guest]

1. The caps are placed randomly, each colour having the same probability and colour of each person's cap is independent of all others.

2. Therefore, any strategy, including one of same colour, or colour on the guy to the left, ... will not work.

3. Everybody need to take a chance by speaking out randomly any of the three colours.

4. Probability of 0 correct answer is (2/3)^28 = .000011734

5. Probability of exactly one correct answer = 28 * (1/3) * (2/3)^27 = .000164

6. And so on, Prob of exactly 2 correct answer is .001109, 3 correct answer = .004805, 4 correct answer = .015016

7. Therefore, Prob of 4 or less correct answer = .021106 = 2.1106%

Hard luck guys ...

[Guest]

Every prisoner should guess that his hat is the color of the person to his left. The likelihood that there are more than four hats of the same color next to each other is small. I'll let the mathematicians do the statistics...

Good idea, but it doesn't work. It brings the same miniscule chance of success as guessing randomly, or everyone guessing the same color.

[Guest]

1. The caps are placed randomly, each colour having the same probability and colour of each person's cap is independent of all others.

2. Therefore, any strategy, including one of same colour, or colour on the guy to the left, ... will not work.

3. Everybody need to take a chance by speaking out randomly any of the three colours.

4. Probability of 0 correct answer is (2/3)^28 = .000011734

5. Probability of exactly one correct answer = 28 * (1/3) * (2/3)^27 = .000164

6. And so on, Prob of exactly 2 correct answer is .001109, 3 correct answer = .004805, 4 correct answer = .015016

7. Therefore, Prob of 4 or less correct answer = .021106 = 2.1106%

Hard luck guys ...

1. True

2-3. False. There are strategies that do work, and we need to find the best one.

4-7. True if guessing randomly.

For quick reference, see bonanova's example of two hat colors in post #17. It satisfies the statement that each hat is assigned randomly, but still there is a strategy that always yields exactly 50% correct guesses.

[araver]

Hmm, very very interesting one.

My first thought is that the underlying idea may be to use a guessing function that acts like a "hard" separator (as in some other puzzles of the "same" type) : when at least X are correct, then all are correct, leaving a lot of cases or all (or most of all) are incorrect. By grouping together the correct guesses in the same scenario, intuitively, one maximizes the likelihood of all guessing incorrectly.

A couple of runs on smaller versions would probably make the above point clearer:

1) For 2 players, one can guarantee 2/3 chance of all guessing incorrectly with f₂(X)=X or informally each guesses the other's color. Out of 9 cases, in 6 of them none is correct and in 3 of them (RR, BB, WW) both are correct.

2) For 3 players, one can guarantee 2/3 chance of all guessing incorrectly with a similar function f₃(X,X)=X, f₃(X,Y)=Z.

This would get 3 correct guesses in all 3-0-0 situations and 2-1-0 situations and 0 correct guesses in the rest of the cases. 2/3 chance of getting "all wrong".

Now this "one fails, then all fail" intuitive grouping looks more likely to be optimal in problems where a win is defined as all guess incorrectly. If one could push it above n=3. That means finding a (rare) code over F₃ⁿ and instructing each of the players to compute their hat color as the "nearest" codeword given the other n-1 hats they can see.

But this particular problems asks for a finer point. Not getting "all wrong", but getting "all but 4 wrong".

Denoting N= no. of players and M = no. of maximum correct guesses, the (general) problem has a natural size attached to it - (M, N). So, the above approach may look fine for (2, 0) and (3, 0), but there seems to be a qualitative leap to reaching (28,4).

Setting optimal aside, a luckier than random shot could be constructed using smaller instances (though composition of smaller instances intuitively destroys optimality in this case). But all of the composition/decomposition-based variants I've toyed with so far led me to nothing in particular. So far. Which is why this post only contains this very rough idea. I actually hoped for a (7,1) solution. Assuming the chance of winning for (7,1) would be alpha, then by composing 4 such instances for the (28,4) problem, one would get a (suboptimal) alpha⁴ There may still be a cleverer way of composing the smaller instances, but I kinda doubt it at this point.

So, I'm back to leaping towards the (28,4) ternary function/code without a clue on how to actually construct it.

Not sure if the above is helpful in any way, :shrug:. Will check back when I get a working (28,4) "code"/function.

[Molly Mae]

...nothing. If Prisoner A could, in some way, communicate the parity of a single hat colour a, we could get a guaranteed 27 incorrect guesses and a 2/3 chance at Prisoner A also getting his incorrect--everyone would know that his hat is either of colour a or not of colour a.

[Anon26]

First thought:

the prisoner counts the number of hats of each colour.

He then writes down the colour which is highest.

This provides atleast adequate probablity that he is wrong

[bushindo]

...nothing. If Prisoner A could, in some way, communicate the parity of a single hat colour a, we could get a guaranteed 27 incorrect guesses and a 2/3 chance at Prisoner A also getting his incorrect--everyone would know that his hat is either of colour a or not of colour a.

Hmm, very very interesting one.

My first thought is that the underlying idea may be to use a guessing function that acts like a "hard" separator (as in some other puzzles of the "same" type) : when at least X are correct, then all are correct, leaving a lot of cases or all (or most of all) are incorrect. By grouping together the correct guesses in the same scenario, intuitively, one maximizes the likelihood of all guessing incorrectly.

A couple of runs on smaller versions would probably make the above point clearer:

1) For 2 players, one can guarantee 2/3 chance of all guessing incorrectly with f₂(X)=X or informally each guesses the other's color. Out of 9 cases, in 6 of them none is correct and in 3 of them (RR, BB, WW) both are correct.

2) For 3 players, one can guarantee 2/3 chance of all guessing incorrectly with a similar function f₃(X,X)=X, f₃(X,Y)=Z.

This would get 3 correct guesses in all 3-0-0 situations and 2-1-0 situations and 0 correct guesses in the rest of the cases. 2/3 chance of getting "all wrong".

Now this "one fails, then all fail" intuitive grouping looks more likely to be optimal in problems where a win is defined as all guess incorrectly. If one could push it above n=3. That means finding a (rare) code over F₃ⁿ and instructing each of the players to compute their hat color as the "nearest" codeword given the other n-1 hats they can see.

But this particular problems asks for a finer point. Not getting "all wrong", but getting "all but 4 wrong".

Denoting N= no. of players and M = no. of maximum correct guesses, the (general) problem has a natural size attached to it - (M, N). So, the above approach may look fine for (2, 0) and (3, 0), but there seems to be a qualitative leap to reaching (28,4).

Setting optimal aside, a luckier than random shot could be constructed using smaller instances (though composition of smaller instances intuitively destroys optimality in this case). But all of the composition/decomposition-based variants I've toyed with so far led me to nothing in particular. So far. Which is why this post only contains this very rough idea. I actually hoped for a (7,1) solution. Assuming the chance of winning for (7,1) would be alpha, then by composing 4 such instances for the (28,4) problem, one would get a (suboptimal) alpha⁴ There may still be a cleverer way of composing the smaller instances, but I kinda doubt it at this point.

So, I'm back to leaping towards the (28,4) ternary function/code without a clue on how to actually construct it.

Not sure if the above is helpful in any way, :shrug:. Will check back when I get a working (28,4) "code"/function.

//

I'm going to come out and admit that the phrase '4 or less correct' is a red herring =). I have a winning rate of 2/3, and I believe avaver and molly are on a cusp of getting that solution.