Je leest:

Maximale overhang

Maximale overhang

Auteur: | 30 maart 2011

Hoe moet je n identieke tegels op de rand van een tafel stapelen, opdat de toren zo ver mogelijk over de tafel helt? Een team van vijf wiskundigen bedacht een nieuwe kijk op dit klassieke vraagstuk uit de wiskunde en wonnen daarmee de David P. Robbins Prize van de Mathematics Association of America.

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.

Medium
De oplossing: met n tegels kun je een toren bouwen die 1/2 + 1/4 + 1/6 + 1/8 + 1/16 + … + 1/(2n) overhangt. Voor grote waarden van n is dat ongeveer gelijk aan ln(n); hierbij staat ln voor de natuurlijke logaritme.

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.

Medium
Een klassieke stapel van 30 blokken (in oranje) in vergelijking met hetzelfde aantal blokken geconfigureerd als een grillige muur (in grijs) stabiel gehouden door een tegengewicht (in blauw). De grijs-blauwe constructie hangt veel verder over dan de oranje constructie!

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.

Medium
Yuval Peres tijdens de Joint Mathematics Meetings 2011 van de Mathematical Association of America.
Laura McHugh / MAA

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.

Large
Onder: de best haalbare overhang met 3 en met 4 tegels. Ter vergelijking staat erboven de stapeling via de harmonische reeks.

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.

Large
De best haalbare overhang met 20 en met 30 tegels. Ter vergelijking is op de achtergrond de stapeling via de harmonische reeks te zien.

“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.”

Medium
‘Overhangconstructies’ zijn niet alleen theoretisch interessant. Deze foto laat zien hoe de Maya’s dergelijke constructies gebruikten (900 voor Christus) in kraagstenen.
Clark Anderson/ Aqua images, Creative Commons License

Zie ook:

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 30 maart 2011

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.