Suppose you have a coin which could have been altered by a cheat to prefer one side over the other. You're not sure whether it's biased to heads or tails, you just know it's biased. Actually, according to the wikipedia article on coin flipping, coins tend to be slightly biased naturally and it's possible to train yourself to flip a coin slightly more predictably than pure chance. So there you are with a biased coin. Nevertheless, can you use it to produce unbiased tosses?
John Von Neumann1 came up with a remarkable idea: use tosses in pairs. If the first toss of a pair comes up heads and the second tails, call the result of the pair heads. If the first comes up tails and the second heads, call it tails. If both tosses produce the same result (heads/heads or tails/tails), ignore that pair and start over.
The reason this process produces a fair result is that the probability of getting heads and then tails must be the same as the probability of getting tails and then heads, as the coin is not changing its bias between flips and the two flips are independent. By excluding the events of two heads and two tails by repeating the procedure, the coin flipper is left with the only two remaining outcomes having equivalent probability. This procedure only works if the tosses are paired properly. If part of a pair is reused in another pair, the fairness may be ruined. Also, the coin must not be biased so that one side has a probability of zero.
Input
We have used a possibly biased coin to produce a series of tosses, until we can make an unbiased decision according to the method as suggested by Von Neumann. The input contains the outcomes of all coin tosses (heads or tails), each on a separate line.
Output
Given a series of coin tosses as read from the input, the output must contain a sentence describing whether heads or tails wins according to the procedure of Von Neumann.
Example
Input:
tails
tails
heads
tailsOutput:
heads wins