I have a puzzle:
Two groups want to break a tied vote using a simple coin flip, however the only coin they have available is a biased coin (i.e., one side will come up more often than the other). To make matters worse nobody in the room knows (or is willing to admit) how the coin is biased.
Assuming that the coin has two distinct sides, design a method for using only this coin to determine a fair outcome between the two parties.
Initially, I thought, since neither party knows how the coin is biased, then either party could simply randomly guess which side the coin will land on and then they will receive a 50% chance they are correct (and 50% chance they are incorrect). This is assuming they are not influenced by any knowledge that they know for how the coin is biased when randomly deciding (or rather they do not know how it is biased). I even performed a simulation on this for a large amount of trials (live demo in python).
However, I stumbled upon this wikipedia article, which mentions an alternative method.
If a cheat has altered a coin to prefer one side over another (a biased coin), the coin can still be used for fair results by changing the game slightly. John von Neumann gave the following procedure:
- Toss the coin twice.
- If the results match, start over, forgetting both results.
- If the results differ, use the first result, forgetting the second.
I'm just curious: is my method of solving the puzzle a viable solution? It seems so, but I'm not 100% certain.