Coin Puzzle: Predict the Other's Coin

Post by gabemart » Sun, Dec 30, 2012, 3:43 PM UTC

_dps wrote: post #37

gabemart wrote: post #19

Earlier quoted context omitted.

>Why does using your own result improve the odds of winning the game!? I find the result very confusing as well. I suspect the source of this counterintuitiveness is that I over simplified the puzzle when I first read it. I simplified the puzzle to "A attempts to guess B's coin, and B attempts to guess A's coin", whereas in fact the true puzzle is "A and B together try to guess the total set of results". When A and B…

I'm not sure the conditional probability argument explains it. Specifically, given A=H, the probability of (H,H) is the same as the probability of (H,T) so that alone shouldn't inform your guess. I believe the core mechanism at play here is that coordination eliminates the possibility of one player being right and the other being wrong, because one can partition the coin outcomes into "We have the same result" and "W…

Post by _dps » Sun, Dec 30, 2012, 3:48 PM UTC

sold wrote: post #35

Here is a bit harder version of the puzzle, with 100 players instead of 2. 100 prisoners are given either a blue or a red hat, at random. Each prisoner is told colors of every hat except their own, and has to make a guess about his hat with absolutely no communication. They win only if they all guess correctly. They can agree on a strategy beforehand. What is the optimal probability of success?

Post by StavrosK » Sun, Dec 30, 2012, 3:50 PM UTC

_dps wrote: post #43

sold wrote: post #35

Here is a bit harder version of the puzzle, with 100 players instead of 2. 100 prisoners are given either a blue or a red hat, at random. Each prisoner is told colors of every hat except their own, and has to make a guess about his hat with absolutely no communication. They win only if they all guess correctly. They can agree on a strategy beforehand. What is the optimal probability of success?

Following up on my other comment about the power of coordination to eliminate certain failure modes: If everyone guesses randomly they stand a (1/2)^100 chance. If they all guess the majority, with, say, blue as the tie-breaker just to have a deterministic algorithm, then they win twice as often because they capture the all-blues and all-reds cases, each with probability (1/2)^100. I don't know if that's optimal but…

Post by sold » Sun, Dec 30, 2012, 6:33 PM UTC

StavrosK wrote: post #42

sold wrote: post #35

Here is a bit harder version of the puzzle, with 100 players instead of 2. 100 prisoners are given either a blue or a red hat, at random. Each prisoner is told colors of every hat except their own, and has to make a guess about his hat with absolutely no communication. They win only if they all guess correctly. They can agree on a strategy beforehand. What is the optimal probability of success?

At random from a pool of 100 hats, or at random from some undetermined distribution?

Post by raldi » Tue, Jan 01, 2013, 6:21 PM UTC

StavrosK wrote: post #44

raldi wrote: post #40

Earlier quoted context omitted.

Each should guess whatever would make an even number of red hats. That makes it a 50% chance they're all wrong, and a 50% chance they're all correct -- thus consolidating all their "rightness" into a single block of probability.

That assumes a uniform distribution. If there were more red hats than blue hats in general, it would be more advantageous for everyone to always guess whatever makes an even number of the majority color, as they would win more than 50% of the time.