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?

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\le s\le 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 $\lceil \frac{n}{e}\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\mathrm{\%}$ 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 $\lceil \frac{14}{e}\rceil =\lceil 5.15\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\le n\le 40$) dat aangeeft hoeveel kikkers er zijn. Daarna volgen de scores $s\in \mathbb{R}$ ($0\le s\le 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

Bronnen

• Gaither CC (1999). Practically speaking: a dictionary of quotations on engineering, technology and architecture. CRC Press. ²

• Grimm J, Grimm W (1912). Household Tales by Brothers Grimm. J.M. Dent & Sons Ltd. ³

• Székely GJ (1987). Paradoxes in Probability Theory and Mathematical Statistics (Mathematics and its Applications). Springer. ⁴