Vraag 9Blikstapelingen

foto Bij het spel blikgooien krijgt de speler één of meer ballen waarmee hij of zij moet proberen zoveel mogelijk blikken 1 van een toren af te gooien. Zo’n toren is altijd op dezelfde manier opgebouwd: op de onderste laag staat 2 3 een aantal blikken en op de lagen erboven steeds één minder. Op de foto zie je een toren met zes blikken. 4 5 6 We nemen in deze opgave aan dat, als een bal de toren raakt, de onderste laag in zijn geheel blijft staan. Neem aan dat een geraakt blik ook werkelijk van de toren afvalt en nooit “mooi” op een lager gelegen laag terechtkomt en ook dat blikken niet blijven staan als één of meer blikken eronder wegvallen. Lars gooit één bal naar een toren met zes blikken, zoals op de foto. Na zijn worp blijft de onderste laag van drie blikken staan. Er zijn nu vijf mogelijkheden voor de overgebleven toren. Drie van deze mogelijkheden zijn in figuur 1a, 1b en 1c schematisch getekend. figuur 1a figuur 1b figuur 1c

We gaan in deze opgave deze situatie wat theoretischer bekijken. We tellen het aantal mogelijke stapelingen van blikken op een onderste laag van n blikken. Hierbij staat vanaf de tweede laag ieder blik steeds boven op twee onderliggende blikken. We nemen steeds aan dat er één keer gegooid is en dat de hele onderste laag is blijven staan. Voor n = 1 is er maar één blik, dus is er ook één mogelijke stapeling. Voor n = 2 zijn er twee mogelijke stapelingen. Zie figuur 2. figuur 2 Je kunt nu met een redenering nagaan dat het aantal mogelijke stapelingen voor n = 3 gelijk is aan 5. Deze redenering gaat als volgt: − Er is één manier met 3 blikken op de onderste laag en 0 blikken op de tweede laag. − Er zijn twee manieren met 3 blikken op de onderste laag en 1 blik op de tweede laag. − Er is één manier met 3 blikken op de onderste laag en 2 blikken op de tweede laag (figuur 1b). − Er is één manier met 3 blikken op de onderste laag, 2 blikken op de tweede laag en 1 blik op de derde laag (figuur 1a). Dat is samen 1 + 2 + 1 + 1 = 5 mogelijkheden. Voor n = 4 is het aantal mogelijke stapelingen gelijk aan 14.

De Belgische wiskundige Charles Catalan ontdekte in de 19e eeuw de volgende formule: C = C · C + C · C + C · C + ... + C · C + C · C met C = 1 n 0 n − 1 1 n − 2 2 n − 3 n − 2 1 n − 1 0 0 Hierin is C het aantal mogelijke stapelingen met n blikken op de n onderste laag.

Voor deze rij getallen, de zogenaamde Catalan-getallen, bestaat geen directe formule. Wel bestaat er een formule die voor grote waarden van n 1,386 · n − 1,5 de Catalan-getallen benadert. Deze formule is B = 0,564 · e · n , n e waarbij B een benadering is van het n Catalan-getal ( C ). n n De getallen voor B worden snel groter. Hoe snel dit gaat, is te n berekenen met behulp van de afgeleide van B . Er geldt (bij benadering): n 1,386 · n − 1,5 1,386 · n − 2,5 B ' = 0,782 · e · n − 0,846 · e · n n

Vanaf een bepaald aantal blikken zal het aantal mogelijke stapelingen met meer dan 500 000 toenemen als de onderste laag met één blik toeneemt.

Onderzoek met behulp van de afgeleide van B vanaf welk aantal blikken n op de onderste laag dit is.