The puzzle: The umpire at a Bears-Colts game has a coin, but he's pretty sure that it's not a fair coin (that is, he's pretty sure that the proportion of time that it comes up heads is not a half). Unfortunately, he has no idea what proportion of the time it does come up heads, and he has no time to experiment - Peyton Manning and Jay Cutler are already standing at the 50 yard line, waiting for the coin toss.
How can the umpire use the biased coin to get a fair coin toss (and in the process protect the integrity of the NFL)?
A solution: Here's a solution that was first noticed by the great polymath John Von Neumann. Let p be the probability that the coin comes up heads. Then in two successive tosses, the probability of HT is p(1-p), while the probability of TH is (1-p)p, exactly the same. So the umpire can toss the coin twice in a row. If it comes up HT, the Bears win, and if it comes up TH, the Colts win. This gives both an equal chance of winning. To make that chance 50%, the umpire just declares that if the coin comes up HH or TT then the experiment is voided and he starts over.
Another solution that was observed by some people: let the umpire put the coin into a random hand behind his back, and replace the coin toss by a game of ``which hand is the coin in?''. Yet another answer observes that if Peyton calls ``Heads'' with probability .5 and ``Tails'' with probability .5, he wins the toss wit probability .5, regardless of the bias (half the time, he wins with probability p, and half the time with probability 1-p, for a net winning probability of p/2 + (1-p)/2 = .5). The problem with these two solutions is that they both assume that the players and umpire can act as ``random number generators'', either fairly picking a hand to hide the coin in, or fairly picking a call. Experience (and experiment) suggests that humans are not all that good at generating predictable randomness!.
A little extra: If you've solved the puzzle, you might want to think about this one (which I think is rather more difficult): after the game, Peyton, Jay and the umpire decide to play Monopoly, but when they open the Monopoly box they find that the dice are missing! How can the umpire use his biased coin (still with unknown bias) to simulate the rolling of two dice, so that the three can play their game?
A solution: There are 56 possible outcomes of tossing the coin 8 times and seeing exactly 3 heads and 5 tails. Each of these has the same probability: p^3(1-p)^5. Declare one of these (say HHHTTTTT) to correspond to the roll (1,1), one of them (say HHTHTTTT) to correspond to the roll (1,2), and so on for each of the other 34 (equally likely) rolls of two dice. Then repeatedly toss the coin eight times in a row until one of the declared 36 strings occurs, and take the corresponding pair to be the roll of the two dice.
Another solution was observed by some people: if you can simulate a fair coin, then you can simulate three consecutive tosses of a fair coin, so you can simulate 8 equally likely occurences. Declare six of these to be equivalent to rol1inh each of 1 through 6, and declare the last two void. You have just simulated the roll of a dice; do it twice to simulate the rolling of two dice.