Ruggegraatstapel

Een stapel op één grondsteen gebouwd, hoe ver kan die oversteken? Het antwoord is er, nu de stapel nog. Ionica Smeets

Wiskundigen dachten dat ze allang wisten hoever een stapel tegels maximaal naar opzij kan uitsteken voordat toren omvalt. Maar informatici Uri Zwick van de universiteit van Tel Aviv en Mike Paterson van de universiteit van Warwick lieten het ongelijk van de wiskunde op dit punt zien. Vorige week presenteerden ze nieuwe stapels op het ‘Symposium on Discrete Algorithms’ in San Fransisco. Eind dit jaar verschijnen hun berekeningen in de American Mathematical Monthly. De nieuwe torens zijn schever dan ooit voor mogelijk werd gehouden.

Het werk van Zwick en Paterson begon met het spel Jenga. Daarin moeten spelers een toren van balkjes bouwen: wie het balkje legt waardoor de toren omvalt heeft verloren. In 2001 analyseerde Zwick welke torens met Jengabalkjes in evenwicht zijn. Het was toen een kleine stap naar de vraag wat de grootst mogelijke ‘overstek’ is. “Natuurlijk kende ik die klassieke vraag”, vertelt Zwick via de telefoon, “maar ik dacht dat alles daarover al lang bekend was.”

In 2005 ging een van de vragen in de nationale wetenschapsquiz nog over de maximale overstek van een stapel stenen. Bouw een toren van vierkante stoeptegels die zo ver mogelijk naar een kant overhelt, zo begon die vraag. De tegels mogen alleen op elkaar gelegd worden, niet naast elkaar. Hoe ver helt hij maximaal over?

oneindig

Het juiste antwoord was: oneindig ver. In een ‘harmonische’ stapel steekt de bovenste steen een halve lengte uit ten opzichte van die daaronder. Die steen steekt zelf een kwart lengte uit en de volgende steen een zesde lengte. Bij n stenen wordt het overstek dan 1/2+1/4+1/6+1/8+1/10+ ... + 1/(2n). Die som gaat naar oneindig als n naar oneindig gaat.

Informaticus Mike Paterson vertelde Zwick dat echter nog niemand wist hoe ver een stapel van n blokken maximaal uitsteekt als je wél met meer dan één blok per laag bouwt, wat bij Jenga mag.

Zwick en Paterson bedachten in eerste instantie de ruggegraatstapel: een enkele stapel verschuivende stenen als ruggegraat, met stenen als tegengewicht op de achterkant van die ruggegraat.

Ze bewezen dat voor 1 tot en met 19 blokken dit soort stapels het maximale overstek geven. Zwick: “We waren ervan overtuigd dat de ruggegraatstapels altijd het grootste overstek zouden geven. We waren anderhalf jaar bezig om dat te bewijzen toen we ineens met de computer vonden we dat voor twintig blokken de beste oplossing er anders uitzag: die had een dubbele ruggegraat.”

Daarna probeerden de informatici stapels in de vorm van een olielamp, een vaas of een parabool. Bij de laatste stapel liggen de stenen steeds om en om als in een muur van bakstenen. De onderste laag begint met één steen en de stapel wordt aan beide kanten langzaam steeds breder – als in een parabool.

logaritme

Hoe groot is het overstek voor deze stapels? In de harmonische stapel is het overstek bij n stenen ongeveer gelijk aan de helft van het natuurlijke logaritme van n. Bij twintig stenen is dat ongeveer anderhalve tegel. Voor paraboolstapels bewezen Zwick en Paterson dat het overstek ongeveer de derdemachtswortel van n is, bij 20 stenen geeft dat 2,7 tegels. Het verschil tussen de stapelvormen neemt enorm toe bij grotere aantallen: om een overstek van 15 tegels te halen, heb je in een harmonische stapel 5000 miljard tegels nodig, bij een ruggegraatstapel 1,2 miljoen en bij een paraboolstapel een luttele 17.200.

Zwick en Paterson bewezen samen met drie andere wiskundigen dat het onmogelijk is om meer dan zes keer de derdemachtswortel van n aan overstek te halen. De vraag is nog hoe die stapel er eigenlijk uit ziet, want hij is nog niet gebouwd.