In een vijver groeit een waterplant die elke dag exact verdubbelt in oppervlak. Na 16 dagen is het gehele wateroppervlak bedekt met de plant. Na hoeveel dagen was de vijver precies voor de helft gevuld?

Bij het ontwikkelen van algoritmes gaat het vaak over de zogenaamde ordercomplexiteit van die algoritmes. Deze geeft aan hoe een algoritme zich gemiddeld gedraagt als het probleem dat je ermee probeert op te lossen groter wordt. Een typisch voorbeeld gaat over het sorteren van rijen van getallen. Stel dat het sorteren van een rij van 100 getallen een seconde duurt, het sorteren van een rij van 101 getallen twee seconden en een rij van 102 getallen vier seconden, dan zie je dat het algoritme een exponentiële ordercomplexiteit heeft: steeds als je de rij 1 getal langer maakt, duurt het twee keer zo lang om de rij te sorteren.

Mensen kunnen zich moeilijk een voorstelling maken van de implicaties van exponentiële groei. Dat blijkt bijvoorbeeld uit het raadseltje hierboven: de vijver is namelijk na 15 van de 16 dagen voor de helft gevuld met de plant. Veel mensen schatten dat dat moment veel eerder al plaatsvindt. Bijvoorbeeld na 10 dagen, maar dan is de vijver pas voor 10% gevuld!

Maar er zijn volgens mij betere manieren om de snelheid waarmee exponentiële groei uit de hand loopt te laten zien. Bij een oefeningetje dat ik ooit in de klas deed, liet ik studenten inschatten hoe vaak ze een A4’tje konden dubbelvouwen. Zoals je je kunt voorstellen, halveert bij elke vouw het A4’tje in omvang (daar komt zelfs het hele A0-A1-A2-A3-A4-etc-systeem vandaan!). Je loopt al vrij snel tegen een fysieke beperking aan: de “bocht” die het papier moet maken wordt op een gegeven moment zo groot dat nog een keer dubbelvouwen niet meer gaat. Als dat echter wel zou lukken, en je zou gewoon kunnen blijven doorgaan met vouwen, hoe dik denk je dan dat het papiertje is wanneer je het 42 keer hebt dubbelgevouwen? Denk daar maar even over na.

Recentelijk kwam ik een ander mooi voorbeeld tegen waarin een poging wordt gedaan om uit te leggen hoe groot getallen kunnen worden. Het gaat hier om een normale stok kaarten en de vraag op hoeveel verschillende manieren je die 52 kaarten kunt sorteren. Het rekensommetje is vrij simpel: 2 kaarten kun je maar op 2 manieren sorteren (ofwel de ene ligt bovenop, ofwel de andere), 3 kaarten kun op 3 keer zo veel manieren sorteren (namelijk 6), 4 kaarten kun je weer 4 keer zo veel manieren sorteren (namelijk 24) en 5 kaarten op weer 5 keer zoveel (namelijk 5).

Het aantal manieren waarop je tweeënvijftig kaarten kunt sorteren is dus 52 * 51 * 50 * 45 * … * 2 * 1, oftewel 52 faculteit (geschreven als 52!). En dat is heel vaak.

En nu komt het mooie verhaal, want om een klein beetje een gevoel te krijgen voor hoe groot dat getal is, heeft de schrijver van dit artikel een leuk voorbeeld bedacht:

Stel je voor dat je een timer hebt die precies 52 faculteit seconden aftelt. Ga op ergens op de evenaar staan en start de timer. Zet nu elke miljard jaar (ja, het gaat even duren) een stap over de evenaar. Zodra je de hele evenaar rond bent, haal je 1 (één) druppel water uit de Stille Oceaan. Ga door tot die oceaan leeg is en leg een A4’tje neer naast je beginpunt op de evenaar. Begin opnieuw (vergeet niet de druppels weer in de oceaan te gooien!) en leg als de oceaan weer leeg is een tweede A4’tje op de stapel. Ga hiermee door tot de papierstapel van de aarde tot de zon rijkt (dat kan een praktisch probleem opleveren, maar je hebt even de tijd om over een oplossing na te denken). Gooi de stapel weg en herhaal dit hele proces 1000 keer.

Klaar? Nee, de timer heeft pas ongeveer 1/3 van de tijd afgetikt.

Wow.

En hoe dik denk je dat ’t eerste A4’tje uit dit verhaal, dat de studenten 42 keer hebben dubbelgevouwen is geworden? Kun je het inschatten?

Je stapel botst hier tegenaan (wist je al dat die website bestond, trouwens? mooi he? je kunt je prima voorstellen dat je ’n liedje gaat zingen als je daar bent, toch? hij wel in elk geval!)