3 ms·
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
by sold 14y ago
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?
- raldi 14y agoEach 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.
- sold 14y agoIndeed, this is the solution. (One can also note that for for the original puzzle of two prisoners, guessing parity reduces to checking whether their hats are the same or different.)
- StavrosK 14y agoThat 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.
- raldi 14y agoI'm not following. With 100 hats, an even number of one color means there's an even number of the other color, too.
- StavrosK 14y agoYeah, sorry, I'm mistaken. If one color is more probable than the other, you can win more by guessing odd rather than even, but you'd have to know the distribution. If you got 51 red hats every time, for example, you'd never win making even hats. For this to work, however, you'd have to know the exact expected probability of each hat (and if it was even or odd), which is improbable.
- StavrosK 14y agoAt random from a pool of 100 hats, or at random from some undetermined distribution?
- sold 14y agoEach hat is independently red-blue 50/50.
- _dps 14y agoFollowing 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 :)]
- StavrosK 14y agoraldi's suggestion below looks reasonable, and brings it up to 50%.