Als prinses krijg je de godganse dag kikkers te zien, waarvan je er uiteindelijk één moet kussen. Je ziet slechts één kikker tegelijkertijd en als je weigert om die te kussen dan krijg je hem nooit meer opnieuw te zien. Kus je de kikker wel, dan zit je voor eeuwig en altijd met die prins opgescheept. Maar hoe kan je weten wanneer je de hoop moet opgeven om de kikkerprins van je dromen tegen te komen en best tevreden kunt zijn met de kikker die je in je handen hebt?

de kikkerprins
Brothers Grimm (1912). The Frog-Prince1. In Household Tales by Brothers Grimm. J.M. Dent & Sons Ltd. Illustratie door Robert Anning Bell.

Gábor Székely schrijft hierover in Paradoxes in Probability Theory and Mathematical Statistics (1986):

Verrassend genoeg is er een methode die ongeveer 37% kans oplevert om uit een reeks van $$n$$ kikkers de knapste kikkerprins te kussen, als je de kikkers één voor één te zien krijgt, je slechts één kikker mag kussen, en je onmiddellijk moet beslissen of je de kikker die je voor je ziet kust of niet.

Hiervoor moet je uitgaan van de volgende strategie. Telkens je een kikker te zien krijgt, geef je hem een score $$s \in \mathbb{R}$$ ($$0 \leq s \leq 1$$) die aangeeft hoe knap je de kikker vindt. Hoe hoger de score, hoe knapper je de kikker vindt. De eerste $$\lceil \frac{n}{e} \rceil$$ kikkers kus je niet, maar je onthoudt wel de hoogste score die je aan die kikkers hebt gegeven. Daarna kus je de eerstvolgende kikker die een hogere score heeft dan de hoogste score van de eerste $$\left\lceil \frac{n}{e} \right\rceil$$ kikkers. Als je de laatste kikker te zien krijgt, dan moet je die wel kussen ongeacht hoe mooi of lelijk je hem vindt.

Deze strategie geeft je $$\frac{1}{e} \approx 37\%$$ kans om de kikker met de hoogste score te kussen, ongeacht hoe groot $$n$$ is. Als er bijvoorbeeld 14 kikkers in het bos zitten, dan negeer je de eerste $$\left\lceil \frac{14}{e} \right\rceil = \left\lceil 5.15 \right\rceil = 6$$ kikkers en kus je de eerstvolgende kikker die een hogere score heeft dan elk van de eerste 6 kikkers.

Invoer

De eerste regel bevat een getal $$n \in \mathbb{N}$$ ($$8 \leq n \leq 40$$) dat aangeeft hoeveel kikkers er zijn. Daarna volgen de scores $$s \in \mathbb{R}$$ ($$0 \leq s \leq 1$$) die aan de $$n$$ kikkers gegeven worden, elk op een afzonderlijke regel.

Uitvoer

De score $$s$$ van de kikker die uiteindelijk door de prinses zal gekust worden, als ze de strategie volgt die hierboven staat beschreven.

Voorbeeld

Invoer:

14
0.0056
0.7911
0.4679
0.3439
0.5503
0.5688
0.3085
0.9156
0.5654
0.2818
0.1636
0.4068
0.9669
0.1147

Uitvoer:

0.9156

Epiloog

Op een zekere dag liep een jongeman langs de weg toen hij plots werd aangesproken door een kikvors

Jongen, als je me kust, dan verander ik in een beeldschone prinses.

De jongeman raapte de kikvors op, lachte ernaar en stopte haar in zijn broekzak. Een poosje later zei de kikvors

Jongen, als je me kust en me in een beeldschone prinses verandert, dan mag je met me trouwen.

De jongeman nam de kikvors uit zijn broekzak, lachte ernaar en stopte hem daarna terug. Nu begon de kikvors zich echt boos te maken.

Jongen, wat is er aan de hand?

riep de kikvors

Ik heb je gezegd dat ik een beeldschone prinses ben, en dat je met me mag trouwen als je me kust!

De jongeman nam de kikvors uit zijn broekzak en zei

Kijk, ik ben een ingenieur. Ik heb geen tijd voor een vriendin, maar een pratende kikvors vind ik cool!
de kikkerprins
De kikkerprins.

Bronnen