Re:Coin Puzzle: Predict the Other's Coin
by _dps on Sunday December 30, 2012 @10:48AM
(#4985989)
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 I always find these "improve random outcomes even with really stupid coordination mechanisms" situations amusing. If there's something better to be done I'd be curious to know :)
[Edit: raldi's clever answer that partitions by parity eliminates all but the we're-all-right and we're-all-wrong outcomes, and is clearly superior :)]
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 I always find these "improve random outcomes even with really stupid coordination mechanisms" situations amusing. If there's something better to be done I'd be curious to know :)
[Edit: raldi's clever answer that partitions by parity eliminates all but the we're-all-right and we're-all-wrong outcomes, and is clearly superior :)]