[Guest]

This is my favourite brain teaser, and one of the most difficult that I know. I apologize if it has been posted before and I missed it.

A team of 15 takes part in a contest. They know each other and all the rules of the contest, and they have time to make their strategy before the actual contest starts.

The rules of the contest are:

1. The players sit in a circle, so that everybody sees everybody. Then the players are blindfolded.

2. On each player's head, either a red or a blue cap is placed. The colour of the cap is determined completely arbitrarily, e.g. by coin toss.

3. The blindfold is removed, and everybody has to write on a piece of paper the answer to the question "What is the colour of your cap?". The answer must be "RED", "BLUE" or "---". Everybody has to write down their answer at the same time.

4. Everybody shows the paper at the same time.

5. The players do not cheat. (They do not exchange information through words, utterances, signs, facial expressions, delays in writing their answer, etc.)

The procedure of the contest is done only once. The team wins the contest if at least one answer is correct and no answer is incorrect. "---" is considered a neutral answer, neither right nor wrong.

Examples:

if team member #12 correctly answers RED, and everybody else answers "---", they win.

if all members answer correctly (RED/BLUE), except for member #12 (who said RED and had blue), they lose.

Which is the strategy with the biggest chance to win, and how high is that chance?

Have fun!

[P.S.] For those who know Romanian, this and many other brainteasers are to be found at www.chichitza.com and www.chichitza.com/forum

As for chess, a section in English is www.chichitza.com/chess.html . It contains puzzles and studies. Some studies may be more difficult for computers than for humans

[Guest]

This is my favourite brain teaser, and one of the most difficult that I know. I apologize if it has been posted before and I missed it.

A team of 15 takes part in a contest. They know each other and all the rules of the contest, and they have time to make their strategy before the actual contest starts.

The rules of the contest are:

1. The players sit in a circle, so that everybody sees everybody. Then the players are blindfolded.

2. On each player's head, either a red or a blue cap is placed. The colour of the cap is determined completely arbitrarily, e.g. by coin toss.

3. The blindfold is removed, and everybody has to write on a piece of paper the answer to the question "What is the colour of your cap?". The answer must be "RED", "BLUE" or "---". Everybody has to write down their answer at the same time.

4. Everybody shows the paper at the same time.

5. The players do not cheat. (They do not exchange information through words, utterances, signs, facial expressions, delays in writing their answer, etc.)

The procedure of the contest is done only once. The team wins the contest if at least one answer is correct and no answer is incorrect. "---" is considered a neutral answer, neither right nor wrong.

Examples:

if team member #12 correctly answers RED, and everybody else answers "---", they win.

if all members answer correctly (RED/BLUE), except for member #12 (who said RED and had blue), they lose.

Which is the strategy with the biggest chance to win, and how high is that chance?

Have fun!

[P.S.] For those who know Romanian, this and many other brainteasers are to be found at www.chichitza.com and www.chichitza.com/forum

As for chess, a section in English is www.chichitza.com/chess.html . It contains puzzles and studies. Some studies may be more difficult for computers than for humans

Assuming that there is no limitations on number of caps of either color (i.e., they might be wearing all red or all blue), it would be wise to

Appoint a leader. This leader would check which color is appearing lesser number of times on others heads and would write that color. All others should write '---'.

Assumption here is that on a fair coin toss both colors should have same probability of repetition.

[Guest]

Assuming that there is no limitations on number of caps of either color (i.e., they might be wearing all red or all blue), it would be wise to

Appoint a leader. This leader would check which color is appearing lesser number of times on others heads and would write that color. All others should write '---'.

Assumption here is that on a fair coin toss both colors should have same probability of repetition.

I came up with a similar solution except

they do want to assign one person to make the guess, but it doesn't matter what color the other hats are. Even if the "leader" was looking at all red hats, he would still have a 50/50 chance of having red or blue.

[Guest]

Assuming that there is no limitations on number of caps of either color (i.e., they might be wearing all red or all blue), it would be wise to

Appoint a leader. This leader would check which color is appearing lesser number of times on others heads and would write that color. All others should write '---'.

Assumption here is that on a fair coin toss both colors should have same probability of repetition.

That strategy is not really required:

..if each cap is decided with a coin toss, the color of the cap on the leader's head is completely independent from what he/she sees. In other words, even if the leader sees 14 REDs, the probability that the leader will have a RED is still half. So the strategy is not better than a random guess.

[Guest]

have one team member wear mirrored sunglasses and seat across from him/her the team member with the best eyesight. Have all team members answer '---' except for the eagle-eyed member who will look in the sunglasses of the member sitting opposite him/her and write down which color he/she sees in their reflection. 50-100% chance of success depending on distance, eyesight, atmospheric disturbances, temporary blindness, retinal detachment, etc.

[wolfgang]

Is it allowed to only one person to change his place?

If yes,,It will be very easy.

[Guest]

Seems that Fast Reply is not working for me. Sorry if this appears multiple times.

Everyone but one select person writes "--". When the masks are removed, everyone looks at the selected person if that person is wearing red and looks at others if blue. Selected person therefore knows what color to write. People are looking at me - Red, otherwise Blue.

Edited December 7, 2010 by SteveK

[Guest]

have one team member wear mirrored sunglasses and seat across from him/her the team member with the best eyesight. Have all team members answer '---' except for the eagle-eyed member who will look in the sunglasses of the member sitting opposite him/her and write down which color he/she sees in their reflection. 50-100% chance of success depending on distance, eyesight, atmospheric disturbances, temporary blindness, retinal detachment, etc.

Seems that Fast Reply is not working for me. Sorry if this appears multiple times.

Everyone but one select person writes "--". When the masks are removed, everyone looks at the selected person if that person is wearing red and looks at others if blue. Selected person therefore knows what color to write. People are looking at me - Red, otherwise Blue.

Remember:

5. The players do not cheat.

To put the problem another way, all players of the team are housed in separate rooms. Everyone is informed about the colour of all others' caps by an arbiter. There is absolutely no possibility of learning more information than those colours.

Edited December 7, 2010 by Kornrade

[bushindo]

Remember:

5. The players do not cheat.

To put the problem another way, all players of the team are housed in separate rooms. Everyone is informed about the colour of all others' caps by an arbiter. There is absolutely no possibility of learning more information than those colours.

How about this strategy

Let's make it easy on ourselves and call the state of the hats 0 and 1.

Every participant look and sum up all the hat state. The sum should be between 0 and 14.

If a participant see a sum that is odd, abstain from guessing.

If a participant see a sum that is 0, 2, 4, or 6, guess that his hat state is 1.

If a participant see a sum that is 8, 10, 12, or 14, guess that his hat state is 0.

This way, the winning rate is about 3/5.

Edited December 7, 2010 by bushindo

[Guest]

That strategy is not really required:

..if each cap is decided with a coin toss, the color of the cap on the leader's head is completely independent from what he/she sees. In other words, even if the leader sees 14 REDs, the probability that the leader will have a RED is still half. So the strategy is not better than a random guess.

Provided the user knows information of other 14 hats, wouldn't it be much safer to calculate probability using this information. In other words, what is the probability that both the children are girls when you already know one of them is a girl? Most people say it is 1/3 while few debate it would remain 1/2. For this puzzle I will go with the first option, as otherwise the best strategy will be - all except one predesignated person taking a guess with 1/2 probability. Not much of a strategy if you ask me.

[Guest]

Remember:

5. The players do not cheat.

To put the problem another way, all players of the team are housed in separate rooms. Everyone is informed about the colour of all others' caps by an arbiter. There is absolutely no possibility of learning more information than those colours.

Mirror in the room, not cheating; just not handled by the rules.

Arbiter gives away the cap's color, not a team member; so again, not handled by the rules.

The statement "There is absolutely no possibility of learning more information than those colours," makes the game impossible to win without wild guessing; so, either the statement is false and one can deduce the color of his/her own cap or it is true and there is no point in trying to figure out the game as it is always a 1/3 chance of winning (possibilities are correct, incorrect, abstain).

[Guest]

How about this strategy

Let's make it easy on ourselves and call the state of the hats 0 and 1.

Every participant look and sum up all the hat state. The sum should be between 0 and 14.

If a participant see a sum that is odd, abstain from guessing.

If a participant see a sum that is 0, 2, 4, or 6, guess that his hat state is 1.

If a participant see a sum that is 8, 10, 12, or 14, guess that his hat state is 0.

This way, the winning rate is about 3/5.

how you got the probability of 3/5?

[Guest]

How about this strategy

Let's make it easy on ourselves and call the state of the hats 0 and 1.

Every participant look and sum up all the hat state. The sum should be between 0 and 14.

If a participant see a sum that is odd, abstain from guessing.

If a participant see a sum that is 0, 2, 4, or 6, guess that his hat state is 1.

If a participant see a sum that is 8, 10, 12, or 14, guess that his hat state is 0.

This way, the winning rate is about 3/5.

This strategy may give a "little more than 50%" winning chance, but it is still far from the optimal solution.

Edited December 7, 2010 by Kornrade

[Guest]

Mirror in the room, not cheating; just not handled by the rules.

Arbiter gives away the cap's color, not a team member; so again, not handled by the rules.

The statement "There is absolutely no possibility of learning more information than those colours," makes the game impossible to win without wild guessing; so, either the statement is false and one can deduce the color of his/her own cap or it is true and there is no point in trying to figure out the game as it is always a 1/3 chance of winning (possibilities are correct, incorrect, abstain).

No mirror in the room, no other sources of indirect information

The arbiter communicates which team member was which colour, just as if they stood in the circle and everyone could see everyone else.

"makes the game impossible to win without wild guessing"

Whoever chooses to write RED/BLUE has a 50% chance of being wrong because of the statistical independence of coin toss events (that was already established). I never said that the team wins 100%!

[bushindo]

This strategy may give a "little more than 50%" winning chance, but it is still far from the optimal solution.

Well, I see what you're saying.

Modify the decision table as below. Only the bottom half is listed, the top part is similar

Sum       Decision

...

7         Abstain

8         Guess 0

9         Guess 1

10        Abstain

11        Guess 0

12        Guess 1

13        Abstain

14        Guess 0

The winning change is now 2/3. Is that still far from optimal?

Edited December 7, 2010 by bushindo

[Guest]

Yes...

The winning percentage for the optimal strategy is well over 70%

[Guest]

If the distribution of the caps is entirely random, then the probability of having a red/blue cap is ALWAYS 0.5 regardless of the other teammembers' color. Hence, the best strategy is for all but one to write down "---" while the 15th player will either write "blue" or "red", whatever he likes most. That team will have a probability of 0.5 of winning the game.

It doesn't matter if a player sees in his teammates that there are 14 blue caps, if it was determined by random, there is a possibility of having the 15th blue cap on my head.

The distribution of reds and blues will be even only after tossing an infinite number of times a fair coin.

[Guest]

Well, I see what you're saying.

Modify the decision table as below. Only the bottom half is listed, the top part is similar

Sum       Decision

...

7         Abstain

8         Guess 0

9         Guess 1

10        Abstain

11        Guess 0

12        Guess 1

13        Abstain

14        Guess 0

The winning change is now 2/3. Is that still far from optimal?

I agree that there is only a 50% chance that a cap will be blue/red regardless of what colour the other caps are, but Bushindo's algorithms are correct in that, the above decision table will bring the probability of winning to 10/16...

It works out

all red hats - lose

1 blue hat - win

2 blue hats - win

3 blue hats - lose

4 blue hats - win

5 blue hats - win

6 blue hats - lose etc...........

[Guest]

over 70%?

with bushido's algorithm you have the following states.

let's make red 0 and blue 1.

all red:

everyone guesses blue, lose

1 blue:

the person who is blue will guess blue, all other abstain. win.

2 blues:

both blues will abstain, all reds will guess blue. lose.

3 blues:

all blues will guess blue, all reds abstain, win

4 blues:

all reds guess blue all blues abstain, lose.

5 blues:

all reds abstain, all blues guess blue, win.

etc.

seems pretty 50/50 to me.

[Guest]

over 70%?

with bushido's algorithm you have the following states.

let's make red 0 and blue 1.

all red:

everyone guesses blue, lose

1 blue:

the person who is blue will guess blue, all other abstain. win.

2 blues:

both blues will abstain, all reds will guess blue. lose.

3 blues:

all blues will guess blue, all reds abstain, win

4 blues:

all reds guess blue all blues abstain, lose.

5 blues:

all reds abstain, all blues guess blue, win.

etc.

seems pretty 50/50 to me.

10/16 is only 62.5%, so if the answer is "over 70%" then it can't be the answer.. but this is how I read the algorithm..

decision 0 = red, decision 1 = blue

so extrapolating from the table (as only the last half is shown)..

Sum Decision

0 1 (blue)

1 - (abstain)

2 0 (red)

3 1 (blue)

4 -

5 0 (red)

etc....

So, if there were two blue hats, each of the blue hats would abstain BUT the red hat users would see 2 blue bats and thus vote red not blue so it would be a win, continuing this through the 16 possible scenarios gives 10 scenarios where the team would win

[Thalia]

100%

1. Take the cap off and look at it. I didn't see anything in the rules against it.

2. If the cap has the thing that sticks out in front, you might be able to see the color if you look up.

Edited December 8, 2010 by Thalia

[Guest]

firstly there are 15 players, not 16, and secondly..

0 1 (blue)

1 - (abstain)

2 0 (red)

3 1 (blue)

4 -

5 0 (red)

etc....

okay

0 blue:

everyone guesses blue: lose

1 blue:

all red abstain, the blue guesses blue, win.

2 blue:

both blues abstain, all reds guess red. win

3 blue:

all blues guess red, all reds guess blue, lose.

4 blue:

all reds abstain, all blues guess blue, win

5 blue:

all blues abstain, all reds guess red win.

so in this case i agree, 2/3 of the time the players win.

my previous post was in response to his first strategy, even 0- 6 blue, even 8-14 red, odd abstain.

Edited December 8, 2010 by phillip1882

[Guest]

firstly there are 15 players, not 16, and secondly..

0 1 (blue)

1 - (abstain)

2 0 (red)

3 1 (blue)

4 -

5 0 (red)

etc....

okay

0 blue:

everyone guesses blue: lose

1 blue:

all red abstain, the blue guesses blue, win.

2 blue:

both blues abstain, all reds guess red. win

3 blue:

all blues guess red, all reds guess blue, lose.

4 blue:

all reds abstain, all blues guess blue, win

5 blue:

all blues abstain, all reds guess red win.

so in this case i agree, 2/3 of the time the players win.

my previous post was in response to his first strategy, even 0- 6 blue, even 8-14 red, odd abstain.

Yes, that's what I got but

in reference to there only being 15 players not 16, you will find working through the above that I was actually referring to the number of possible scenarios, not players, ie. 0 blue hats through to 15 blue hats = 16 possible outcomes

[Guest]

Write down the color of the hat of the person next to them and then pass each note one to the left?

[Guest]

Key to a lot of these types of problems: Make it simple, then expand.

So consider all but 3 people abstain from answering.

These 3 can follow the simple strategy:

1. If the other two colors differ then abstain.

2. If the other two colors are the same, choose the opposite.

With 3 people you have 2^3=8 possibilities:

BBB GBB

BBG GBG

BGB GGB

BGG GGG

For 2/8 (BBB, and GGG) all three will guess incorrectly.

For the other 6, two will abstain and one will guess correctly.

There's your 75%.

Now, I started simple and picked 3. Maybe someone can build on this by take into people into account to raise the percentage?

[Guest]

It seems all the respondents here are treating the coin toss as random event.

A fair coin toss would follow the binomial distribution for probability of a predefined pattern in successive tosses.

So, let's say what are the odds of seeing 7 reds and 7 blues? Coz that's the only 50-50 possibility for the chosen leader to guess wrong.

Whenever this balance is tilted in favor of one color, the leader should chose the other color, to account for balancing nature of binomial distribution.