Het was ooit een vraag in de Wetenschapsquiz van VPRO/NWO:
Wetenschapsquiz 2005, vraag 17:
Bouw een toren van vierkante stoeptegels die zo ver mogelijk naar een kant overhelt. De tegels mogen alleen op elkaar gelegd worden, niet naast elkaar. Hoe ver helt hij maximaal over?
A. Precies twee tegels. B. Ongeveer anderhalve tegel. C. Oneindig ver.
Het was een moeilijke opgave: niet meer dan 17% van de inzenders wist dat de toren willekeurig ver kan overhangen, mits je maar genoeg tegels hebt (antwoord C).
Deze vraag met het verrassende antwoord kent een lange geschiedenis. Al halverwege de negentiende eeuw verscheen het vraagstuk in het boek Elementary Mechanics van J.B. Phear. Na 1923, toen het probleem werd gepubliceerd in het tijdschrift The American Mathematical Monthly, werd het een klassieker in de wiskunde.
De harmonische reeks
Waarom kan de toren oneindig ver overhangen? Het handigst gaat het als je van bovenaf rekent en bouwt. Het zwaartepunt van de bovenste tegel mag niet buiten de tegel eronder vallen, dus een halve tegelbreedte. Dat van de tweede tegel van boven ligt precies op een kwart van de breedte. De derde tegel mag slechts een zesde uitsteken. De vierde een achtste enzovoort. In het algemeen: de k-de tegel (van bovenaf) mag 1/(2k) uitsteken. Dus een toren van n tegels hangt 1/2 + 1/4 + 1/6 + 1/8 + 1/16 + … + 1/(2n) over.
De reeks Hn = 1 + 1/2 + 1/3 + 1/4 + 1/5 + … + 1/n heet de harmonische reeks. Deze reeks groeit traag, maar wordt wel willekeurig groot. De Zwitserse wiskundige Leonhard Euler heeft al in de achttiende eeuw een korte formule gevonden die voor grote waarden van n een heel nauwkeurige benadering van de harmonische reeks geeft:
Hn = 1 + 1/2 + 1/3 + 1/4 + 1/5 + … + 1/n ≈ ln(n) + γ + 1/(2n) + 1/(12n2).
De eerste term, ln(n), geeft aan hoe hard de som groeit. Dit is de natuurlijke logaritme; hij groeit heel langzaam naarmate n toeneemt, maar kan wel willekeurig groot worden. De tweede term, γ, is de zogenaamde constante van Euler-Mascheroni, vaak ook kortweg ‘constante van Euler’ genaamd. Er geldt dat γ = 0,5772156… De laatste twee termen worden kleiner naarmate n groter wordt.
De overhang van de toren van tegels is precies de helft van de harmonische reeks, ½Hn, oftewel ongeveer ½ln(n) en die gaat naar oneindig als n naar oneindig gaat. Dat betekent in theorie, dat elke afstand, hoe groot ook, te overbruggen is. Het aantal benodigde tegels groeit wel exponentieel. Om 1 tegel overhang te bewerkstelligen heb je een toren van 5 tegels nodig (overhang 1,14 tegel). Voor 2 tegels overhang een toren van 32 tegels, voor 3 tegels 227, enzovoort.
Een exponentiële verbetering
Dat je met n tegels een overhang van de orde ln(n) kunt bereiken, is op zichzelf al een uiterst verrassend resultaat: het betekent dat een oneindig hoge toren oneindig ver overhangt. Maar toch: de hoogte van de toren is van de orde en en de vraag is natuurlijk of het zuiniger kan.
Een paar jaar geleden construeerden vijf wiskundigen een toren van n tegels met een overhang van de orde n1/3, iets wat velen niet voor mogelijk hielden. Bovendien toonden de wiskundigen aan dat de orde n1/3 de best mogelijke is. Hun bevindingen werden in twee artikelen gepubliceerd in The American Mathematical Monthly (januari en november 2009); klik hier voor een pdf van het artikel. Nu, twee jaar later, krijgen ze de prestigieuze David P. Robbins Prize voor hun werk, een prijs die sinds 2005 eens in de drie jaar wordt uitgereikt aan wiskundigen die een bijzondere prestatie hebben geleverd in de algebra, combinatoriek of discrete wiskunde.
In de oorspronkelijke formulering wordt een voorwaarde gesteld voor het stapelen: de tegels mogen alleen op elkaar gelegd worden, niet naast elkaar. Voor hun oplossing moesten de wiskundigen, Yuval Peres van Microsoft Research Redmond, Mike Paterson van de University of Warwick, Mikkel Thorup van AT&T Labs, Peter Winkler van Dartmouth College, en Uri Zwick van Tel Aviv University, deze voorwaarde laten varen. Mét die voorwaarde is de klassieke oplossing, met de harmonische reeks, het best haalbare resultaat. Maar als je toestaat dat tegels ook naast elkaar gelegd mogen worden, is een overhang van de orde n1/3 het best haalbare.
De aanpak is om eerst een rommelig ogende muur te bouwen, vol met gaten, en een solide stapel die voldoende tegenwicht biedt. De overhang die zo behaald kan worden, is flink groter dan de klassieke stapeling die van de harmonische reeks uitgaat. De constructie die Peres en zijn collega’s bedachten, levert exponentieel betere resultaten dan de klassieke aanpak.
Hierboven zijn de gevallen n = 3 (links) en n = 4 (rechts) geïllustreerd. Boven staat de klassieke oplossing, onder de oplossing van het team van Peres. Hoe groter n, hoe groter het verschil tussen de twee oplossingen wordt. Hieronder zijn de gevallen n = 20 en n = 30 getekend; in grijs de nieuw gevonden stapeling, in wit de klassieke oplossing.
“Optimalisatieproblemen hebben veel toepassingen”, zegt Peres. “Denk aan het minimaliseren van wachttijden, het verbinden van een stel processors tegen zo laag mogelijke kosten, het beslissen hoe vaak verschillende websites doorzocht moeten worden bij het vernieuwen van een zoekmachine-index. Het ontwikkelen van nieuwe methoden om zulke problemen op te lossen, is een belangrijk onderdeel van het werk van de theoretische afdeling van Microsoft Research.”
Zie ook:
- Maximum Overhang, Optimum Reward (Eng.)
- The Robbins Prize (Eng.)
- Maximum Overhang (Eng., pdf)