Veronderstel dat je beschikt over een muntstuk 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 gebruikmaken van het muntstuk om op een eerlijke manier te tossen?
John Von Neumann1 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 muntstuk 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
muntUitvoer:
kop wint