Puzzle #3

From Technology Review Magazine and RangeVotingdotorg

Puzzle #3 (interesting – easy once you see it, otherwise hard!):

Three people enter a room and a red or blue mark is made on each person's forehead. The color of each mark is determined by a coin toss, with the outcome of one coin toss having no effect on the others. Each person can see the others' marks but not his own.

No communication of any sort is allowed, except for an initial strategy session before the game begins. Once they have had a chance to look at the other marks, they must (simultaneously) guess the color of their own marks, or pass. The group shares a hypothetical $3 million prize if at least one player guesses correctly and none guess incorrectly.

The problem is to find a strategy for the group maximizing its chances of winning the prize.

For example, one obvious strategy for the players would be for one player always to guess "red" while the others pass. That would give the group a 50% chance of winning the prize. Can the group do better?

Share this

My strategy is that every

My strategy is that every person moves a wall depending on the number and color of the marks on the other people. For instance, two red, go right; two blue, go left; one of each, go to far wall. When someone goes to either the right or the left (as at least one must, with only two colors and three people), the other two know that they have that color represented by that wall.

I wont give away the answer,

I wont give away the answer, but you can get 75% by using a strategy where you distribute your errors intellegently. You each can only have a 50% chance of being right, but if you ensure that only one person is right when you win (the rest pass), and everyone is wrong when your team guesses incorrectly, you can boost your odds.

All, I haven't gone to the

All,

I haven't gone to the trouble of joining the Yahoo group to find the answer, so I don't know if this is the same.

Don't look if you want to analyze some more.

ffffffffffffffffffffiiiiiiiiiiiiillllllllllllllllllll

The problem needs both correct answers and a minimum of wrong answers.

Start with the default of passing, i.e. not voting.

Only vote if you see two of the same color, and vote the opposite. You only have a 50/50 chance of being right.

However, every wrong answer is a case where all three colors are the same. So there are only three total wrong answers, but only two possibilities, red and blue, to contain them.

Since there only 8 possible states and 2 wrong answers, the probability of a right answer is 75%.

Regards, Don

Two problems here. 1st,

Two problems here.

1st, there's doing it with communication, which Brad nicely summarizes. I assume Communication means information transmission of any sort besides looking at the others' marks.

2nd, there's no communication...and you have to hope for probabilities. JFK presents the response I found in a very interesting fashion. 75% is the best I can think of so far.

Brad: That would count as

Brad: That would count as communication and is not allowed.

One argument: If person A sees that persons B and C both have red marks, then chances are his mark is blue, since the odds of all 3 randomly selected marks being the same color is only 1 in 8.

Counterargument: Each coin toss is a separate event. The fact that the results of two coin tosses are known does not change the odds of the third coin toss -- it's still 50/50, not 1 in 8, so it doesn't matter if you can see the the other two marks or not. Result: you cannot possibly improve your odds over 50%.

I'm with Doug. The other

I'm with Doug. The other people are a red herring. You could devolve this down to: you see the results of two coin flips; if you guess the third flip correctly, you win.

Doug & Cornelius, The other

Doug & Cornelius,
The other people are not a red herring, because you define a group strategy before you play. It is true the guess of any one member only has a 50% chance of being correct, however the group strategy can determine WHEN a member does the guessing (remember you can pass). Using this, it is possible to distribute your mistakes. Its important to rememeber that it doesnt matter if you make 1 mistake or 3 mistakes (everyone guessing wrong), so you can use that non-linearity to improve your odds.

It is true the guess of any

It is true the guess of any one member only has a 50% chance of being correct, however the group strategy can determine WHEN a member does the guessing (remember you can pass).

Perhaps I'm being overly pedantic, but the determination of who does the guessing would have to take place before the marking, since all communication -- including saying if you pass or not (since that could be useful information) -- is forbidden.

Good puzzle. I agree that

Good puzzle. I agree that there are eight possible marking scenarios, but no matter what, wouldn't only one person person vote if you cannot have a single incorrect answer? Person #1 has four possibilities (A,D,E and H). Two are correct and two are not. That is 50% not 75%.

1 2 3
A r r r
B r r b
C r b r
D r b b
E b r r
F b r b
G b b r
H b b b

The odds of one person guessing correctly is 50%, two people is 25% and three people is 12.5%. If you have more than one person guess, you need to multiply probabilities rather than add individual outcome probabilities. I think.

Patinator: You don't select

Patinator: You don't select the person to vote beforehand. You decide that if a person sees that the other two have the same color, you guess the opposite color. In cases B, C, D, E, F, and G only one person will guess a color and he will be correct. In cases A and H, all three will guess a color and all three will be wrong.

I'm thinking about Patri's

I'm thinking about Patri's comment, and it looks to me like as you expand this puzzle, the "vote the opposite when you see all the same color, pass otherwise" trick doesn't work anymore. with 4 players, the distribuution is 3-1 only half the time. With more players, it's less than 50% so that you get an (n-1) - 1 distribution, so just letting one player guess and others pass becomes a superior strategy.

If the players can hear the other's answers, you can always get strictly better than 50%. Player 1 passes if everybody else is <predetermined color>, guesses otherwise. Player 2 then knows what to guess if player 1 passes.

If they can hear each other, *and* the order of who answers is determined by the players or in advance (so that player 1 knows who player 2 will be), then player one looks only at player two for a predetermined color and they get 75% each time, just like the 3 player scenario.

The 3 player is prettier though, since you actually need zero communication to get 75%.

FXKLM: I was just using #1

FXKLM: I was just using #1 as the first person who could guess, but I think I got it using brute force.

If #1 passes, that means he can only see scenarios B,C,F and G. If #2 votes (C,F), then he will be correct 100% of the time. If #2 passes, #3 will vote (B,G) and be correct 100% of the time.

If #1 votes, that means he can only see scenarios A,D,E and H. He will be correct 50% of the time.

Therefore, the probability of getting either B, C, F and G OR A, D, E and H is 50%. Combining that with the percent of voting correctly, you get the 75%.

(.50 * 1.00) + (.50 * .50) = .75

Michael, with greater than

Michael, with greater than three players you can still get the 75%, since if you can't come up with a better strategy (I suspect you can't) you can always have player 1-3 use the three player strategy and ignore the other players, and the other players always pass.

1 2 3 A r r r all vote

1 2 3
A r r r all vote b,lose
B r r b 3 votes b, wins
C r b r 2 votes b, wins
D r b b 1 votes r, wins
E b r r 1 votes b, wins
F b r b 2 votes r, wins
G b b r 3 votes r, wins
H b b b all vote r,lose
not states votes are passes

chances of winning: 6 out of 8, or 75%

Impressive Puzzle! Very enjoyable!

3 people only? Yawn. Do it

3 people only? Yawn. Do it for N-people, and you'll derive some interesting coding theory.

Do it for N-people, and

Do it for N-people, and you’ll derive some interesting coding theory.

Not really, it's still 50%.

Patri: 3 people only? Yawn.

Patri: 3 people only? Yawn. Do it for N-people, and you’ll derive some interesting coding theory.

For N people, pick 3 people and use the solution for 3 people.

Oh, okay, sorry. "none guess

Oh, okay, sorry. "none guess incorrectly" - I missed that.

1 2 3 A r r r B r r b C r b

1 2 3
A r r r
B r r b
C r b r
D r b b
E b r r
F b r b
G b b r
H b b b

To restate my previous comment: Three people, 1, 2, 3.

1 and 2 look at 3. They state the color of 3.
3 states the opposite color from 1.

This guarantees a correct result 100% of the time.

A: 1 is r and says r. (because 3 is r and 1 says the color of 3)
B: 3 is b and says b. (because 3 says the opposite of 1 and 1 is r)
C: 1 is r and says r. (because 3 is r and 1 says the color of 3)
D: 2 is b and says b. (because 3 is b and 2 says the color of 3)
E: 2 is r and says r. (because 3 is r and 2 says the color of 3)
F: 1 is b and says b. (because 3 is b and 1 says the color of 3)
G: 3 is r and says r. (because 3 says the opposite of 1 and 1 is b)
H: 1 is b and says b. (because 3 is b and 1 says the color of 3)

Don, Read my whole solution.

Don,

Read my whole solution. It's the whole comment. It's not just the first paragraph.

Solution for 2 people: 1 2 A

Solution for 2 people:

1 2
A r r
B r b
C b r
D b b

1 looks at 2 and says the color of 2.
2 looks at 1 and says the opposite color from 1.

A: 1 is r and says r
B: 2 is b and says b
C: 2 is r and says r
D: 1 is b and says b

Next, my solution for 1 person:

Does the room by any chance have a mirror? :)

The way to most increase

The way to most increase your odds has to be to agree ahead of time to only guess if the other two have the same color. Of course you guess the opposite. This means that the only time more than one person answers is when they all have the same color. Hence, they all answer incorrectly. There is only a 2/8 chance having three consecutive independent coin tosses the same color regardless of the color. This means that 6/8 times the method will work, or in other words 75% of the time you will win.

Three players: A, B, C. A

Three players: A, B, C.

A and B both look at C. If C is blue, both A and B say "blue". If C is red, both A and B say "red".

C looks at A and B. If C sees that A and B are different colors, then C knows that at least one of A and B is going to be correct. But if C sees that A and B are the same color, then A and B will be correct if and only if C is the same color as A and B. Therefore to ensure 100% probability of winning the prize, C picks the opposite color from A and B.

Constant, A and B both look

Constant,

A and B both look at C. If C is blue, both A and B say “blue". If C is red, both A and B say “red".

This produces two right answers for all red and all blue, but some wrong answers for everything else. Result 2 of 8, 25%. To win the prize there can be no wrong answers.

Regards, Don