Op Eerste Kerstdag 2006 werd de dertiende editie van de Nationale Wetenschapsquiz uitgezonden. Vraag 16 luidde als volgt:
Je krijgt achter elkaar in willekeurige volgorde zes taarten te zien van verschillende grootte. Na elke taart moet je beslissen of je deze wilt of niet. Je mag maar één keer ja zeggen. Wat is de beste strategie om de grootste taart te bemachtigen?
a. Je verwerpt de eerste twee mogelijkheden en kiest daarna voor de eerste taart die groter is dan de eerste twee. b. Je verwerpt de eerste vier mogelijkheden en kiest daarna voor de eerste taart die groter is dan de eerste vier. c. Met een dobbelsteen, want het zal altijd een gok blijven.
Dit vraagstuk is een variant op een oude puzzel. Wiskundige Martin Gardner stelde het probleem in 1960 aan de orde in zijn column ‘Mathematical Recreation’ in het februarinummer van The Scientific American. In Gardners context gaat het niet om taarten, maar om secretaresses: wat is de beste strategie om de beste secretaresse te selecteren uit een rij kandidaten, die na elkaar langskomen, waarbij je één keer een kandidaat mag aannemen, en waarbij een voorbijgaande kandidaat later niet alsnog gekozen mag worden?
Martin Garder (geboren 1914), een van de invloedrijkste personen op het gebied van het populariseren van wiskunde. Hij had 25 jaar lang een column in The Scientific American en schreef meer dan zestig boeken.
Drie taarten
Het vraagstuk uit de Wetenschapsquiz kunnen we vereenvoudigen door niet uit te gaan van zes taarten, maar van drie taarten. Je krijgt achter elkaar in willekeurige volgorde drie taarten te zien van verschillende grootte. Na elke taart moet je beslissen of je deze wilt of niet. Wat is dan de beste strategie om de grootste taart te krijgen? Als we het toeval laten beslissen (werp bijvoorbeeld met een dobbelsteen; bij 1 of 2 ogen kies je de eerste taart, bij 3 of 4 ogen kies je de tweede taart en bij 5 of 6 ogen de derde taart), dan bemachtig je met kans 1/3 de grootste taart. Als je de eerste twee voorbij laat gaan, blijft alleen de laatste taart over, die met kans 1/3 de grootste is. Hoe zit het als je de eerste taart voorbij laat gaan, en vervolgens kiest voor de eerste taart die groter is dan die ene taart die je voorbij liet gaan? (Indien de grootste taart de eerste is, kies je noodzakelijkerwijs de laatste taart.)
De drie taarten kunnen in zes verschillende volgordes voorbijkomen. Hieronder zie je de mogelijke volgordes. Met 1 wordt de kleinste taart genoteerd, met 2 de middelgrote taart en met 3 de grootste taart. Als je de eerste taart die langskomt verwerpt, en daarna kiest voor de eerste taart die groter is, dan valt de keuze op de taart die hieronder cursief is weergegeven.
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
Van de zes mogelijke volgordes, zijn er drie die tot het kiezen van de grootste taart leiden. Dat betekent dat de kans op het bemachtigen van de grootste taart gelijk is aan 3/6 = 1/2. De strategie om de eerste taart te verwerpen, leidt ten opzichte van de ‘dobbelsteenmethode’ dus tot een anderhalf keer zo grote kans op het krijgen van de grootste taart!
Vier taarten
Welke strategie moet je kiezen als je vier taarten krijgt te zien? Er zijn dan in totaal 4! = 24 mogelijke volgordes waarin de taarten langs kunnen komen:
1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2
2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1
3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1
4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1
Als je de eerste taart verwerpt en dan kiest voor de eerste taart die groter is, valt de keuze op de cursiefgedrukte taart. In 11 van de 24 mogelijkheden bemachtig je de grootste taart, dus je hebt een ‘grootste-taart-kans’ van 11/24 ≈ 0,4583. Als je de eerste twee taarten verwerpt en dan kiest voor de eerste taart die groter is dan de eerste twee, valt de keuze op de vetgedrukte taart. De ‘grootste-taart-kans’ is dan 10/24 ≈ 0,4167. Het toeval laten beslissen, of de eerste drie taarten voorbij laten gaan, leiden allebei tot een ‘grootste-taart-kans’ van 1/4 = 0,25. Net als bij drie taarten, is de beste strategie om de eerste taart te verwerpen en daarna te kiezen voor de eerste taart die groter is.
n taarten
Bij vijf taarten is het aantal mogelijke volgordes gelijk aan 5! = 120 en bij zes taarten is dat aantal 6! = 720. Het aantal volgordes neemt dus razendsnel toe naarmate het aantal taarten groter wordt. Het uitschrijven van alle mogelijkheden wordt dan welhaast onbegonnen werk. Daarom leiden we hieronder een algemene formule af.
Stel dat er één voor één n taarten van verschillende grootte voorbij komen. Je mag één keer ja zeggen. Je hanteert de volgende strategie: je verwerpt de eerste k taarten en kiest daarna voor de eerste taart die groter is dan de eerste k taarten. Wat is de kans dat je op deze manier de grootste taart bemachtigt? Om deze vraag te beantwoorden, merken we eerst op dat er twee manieren zijn waarbij de keuze niet op de grootste taart valt: 1. de grootste taart bevindt zich onder de eerste k taarten; 2. de grootste taart bevindt zich niet onder de eerste k taarten, maar wordt voorafgegaan door een taart die groter is dan de eerste k taarten.
De grootste taart is de (k+1)de taart De kans dat de grootste taart de (k+1)de taart in de rij is, is gelijk aan 1/n. De kans dat je deze taart kiest, nadat je de eerste k taarten hebt verworpen, is gelijk aan 1. Dus de kans dat je met de (k+1)de taart te grootste taart bemachtigt, is gelijk aan 1/n.
De grootste taart is de (k+2)de taart De kans dat de grootste taart de (k+2)de taart in de rij is, is gelijk aan 1/n. Deze taart wordt gekozen indien de grootste taart van de eerste k+1 taarten zich bevindt onder de eerste k taarten; de kans hierop is gelijk aan k/(k+1). Dus de kans dat je met de (k+2)de taart te grootste taart bemachtigt, is gelijk aan (1/n) • (k/(k+1)) = k/(n(k+1)).
De grootste taart is de (k+3)de taart De kans dat de grootste taart de (k+3)de taart in de rij is, is gelijk aan 1/n. Deze taart wordt gekozen indien de grootste taart van de eerste k+2 taarten zich bevindt onder de eerste k taarten; de kans hierop is gelijk aan k/(k+2). Dus de kans dat je met de (k+3)de taart te grootste taart bemachtigt, is gelijk aan (1/n) • (k/(k+2)) = k/(n(k+2)).
Dit proces zetten we voort tot en met het laatste geval:
De grootste taart is de n-de taart De kans dat de grootste taart de laatste taart in de rij is, is gelijk aan 1/n. Deze taart wordt gekozen indien de grootste taart van de eerste n-1 taarten zich bevindt onder de eerste k taarten; de kans hierop is gelijk aan k/(n-1). Dus de kans dat je met de n-de taart te grootste taart bemachtigt, is gelijk aan (1/n) • (k/(n-1)) = k/(n(n-1)).
Om de ‘grootste-taart-kans’ uit te rekenen, moeten we alle kansen op de gebeurtenissen waarbij de grootste taart in de wacht wordt gesleept, bij elkaar optellen. Deze kans noteren we met pn(k), in woorden: ‘de kans op het bemachtigen van de grootste taart als er in totaal n taarten voorbij komen, waarvan je de eerste k taarten verwerpt’. Er geldt:
(1) pn(k) = 1/n + k/(n(k+1)) + k/(n(k+2)) + … + k/(n(n-1)) = = (k/n)(1/k + 1/(k+1) + 1/(k+2) + … + 1/(n-1)).
Voor verschillende waarden van n kunnen we de ‘grootste-taart-kans’ nu uitreken bij verschillende strategieën. Voor kleine waarden van n lukt dat nog wel met de hand, voor grotere waarden van n kan een computerprogramma als Maple worden gebruikt. Voor n=5 en n=6 zijn dit de resultaten:
p5(1) = 50/120, p5(2) = 52/120, p5(3) = 42/120, p5(4) = 24/120;
p6(1) = 274/720, p6(2) = 308/720, p6(3) = 282/720, p6(4) = 216/720, p6(5) = 120/720.
Het antwoord op de vraag uit de Wetenschapsquiz, het probleem met zes taarten, is dus alternatief a: je verwerpt de eerste twee mogelijkheden en kiest daarna voor de eerste taart die groter is dan de eerste twee. De ‘grootste-taart-kans’ is dan gelijk aan 308/720 ≈ 0,4278.
Honderd taarten
Wat is de beste strategie als er honderd taarten langskomen? Hieronder zie je een grafiek van p100.
De grafiek van pn voor n=100
Uit bovenstaande grafiek blijkt dat de optimale strategie is om 37 taarten te verwerpen. De grootste-taart-kans is dan ongeveer gelijk aan 0,3710; een stuk groter dan 0,01, de grootste-taart-kans indien je het toeval laat bepalen welke taart je kiest!
Asymptotisch gedrag
Bij n taarten is de grootste-taart-kans gelijk aan 1/n; als n heel groot wordt, gaat deze kans naar nul. Wat is het limietgedrag van de grootste-taart-kans als je de eerste k taarten verwerpt, voor de optimale waarde van k? Deze optimale waarde van k zullen we noteren met kn (zoals we eerder zagen, geldt k3 = 1, k4 = 1, k5 = 2 en k6 = 2). In de onderstaande figuur zie je de grafieken van pn(kn) en van kn/n.
De bovenstaande grafieken doen vermoeden dat pn(kn) en kn/n convergeren naar een zekere limietwaarde.
Formule (1) bevat de factor (1/k + 1/(k+1) + 1/(k+2) + … + 1/(n-1)). Deze uitdrukking kunnen we ook als volgt schrijven: (1 + 1/2 + 1/3 + … + 1/(n-1)) – (1 + 1/2 + 1/3 + … + 1/(k-1)). Voor grote waarden van n en k is dit bij goede benadering gelijk aan (ln(n-1) + γ) – (ln(k-1) + γ) = ln((n-1)/(k-1)). Hierbij is γ de constante van Euler-Mascheroni. Formule (1) kan voor grote waarden van n dus worden geschreven als
(2) pn(k) ≈ (k/n) • ln((n-1)/(k-1)) ≈ -k/n • ln(k/n).
In het geval van honderd taarten zie je hieronder de grafieken van de exacte grootste-taart-kans p100(k) en van de benaderde grootste-taart-kans -k/100 • ln(k/100).
De grafieken van de exacte grootste-taart-kans (rood) en de benaderde grootste-taart-kans (groen) voor n=100
Zetten we x = k/n, dan kan formule (2) worden vervangen door
(3) f(x) = -x ln(x).
Met behulp van differentiaalrekening is het niet moeilijk om het maximum van f te bepalen. Het maximum treedt op bij x = 1/e, en de maximale waarde is eveneens 1/e, zie ook onderstaande grafiek.
De grafiek van y = -x ln(x)
Conclusie
Het bijzondere getal 1/e ≈ 0,37 komt twee keer naar voren in het taartenprobleem. Voor grote waarden van n geldt: de optimale strategie om de grootste taart te bemachtigen is om de eerste 37% van het totale aantal taarten te verwerpen en vervolgens te kiezen voor de eerste taart die groter is; de grootste-taart-kans bij de optimale strategie is gelijk aan 0,37.