PROG0493 - Con proofing
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 Neumann 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 tails
Output:
heads wins
Resources
- Stout QF, Warren BL (1984). Tree algorithms for
unbiased coin tossing with a biased coin. Annals
of Probability 12,
212-222.
Veronderstel dat je beschikt over een munstuk waarvan het vermoeden bestaat dat het vervalst is. Je weet niet of de vervalsing in het voordeel speelt van kop of munt. Enkel maar dat één van beide misschien in het voordeel is. Kan je ondanks dit gegeven toch gebruik maken van het muntstuk om op een eerlijke manier te tossen?
John Von Neumann gaf de volgende opmerkelijke oplossing voor dit probleem: gebruik het muntstuk om per twee worpen te tossen. Als de eerste worp kop oplevert en de tweede worp levert munt op, dan noemen we het resultaat van die twee worpen kop. Als de eerste worp munt oplevert en de tweede worp levert kop op, dan noemen we het resultaat van die twee worpen munt. Als beide worpen hetzelfde resultaat opleveren (kop/kop of munt/munt), dan negeren we die twee worpen en beginnen we opnieuw.
De reden waarom deze procedure een eerlijk resultaat oplevert, ligt in het feit dat de kans om kop/munt te werpen gelijk is aan de kans om munt/kop te werpen. Het voordeel van het munstuk verandert immers niet tussen twee worpen en de twee worpen zijn onafhankelijk van elkaar. Omdat we kop/kop en munt/munt als mogelijke uitkomsten negeren door het herhalen van de procedure, blijven er slechts twee mogelijke uitkomsten over die evenveel kans hebben. De procedure werkt alleen maar als de worpen op een correcte manier gepaard worden: als een deel van een paar hergebruikt wordt in een ander paar, dan is de eerlijkheid om zeep. Het muntstuk mag ook niet op zo een manier vervalst zijn dan het onmogelijk is om één van beide zijden als uitkomst op te leveren.
Invoer
We hebben een reeks worpen uitgevoerd met een muntstuk dat mogelijk vervalst is, totdat we op basis van de procedure van Von Neumann een eerlijke beslissing kunnen nemen over welke zijde van het muntstuk wint. De invoer bestaat uit het resultaat van al deze worpen (kop of munt), elk op een afzonderlijke regel.
Uitvoer
Gegeven de reeks worpen zoals ingelezen uit de invoer, moet de uitvoer een zin bevatten die aangeeft of kop dan wel munt wint volgens de procedure van Von Neumann.
Voorbeeld
Invoer:
munt munt kop munt
Uitvoer:
kop wint
Bronnen
- Stout QF, Warren BL (1984). Tree algorithms for
unbiased coin tossing with a biased coin. Annals
of Probability 12,
212-222.
| Added by: | Peter Dawyndt |
| Date: | 2014-08-29 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS