Storingsrekening (1): De koning en het schaakbord

De precieze oorsprong van het schaakspel is onbekend, maar een beroemde legende vertelt dat het spel rond de vijfde eeuw na Christus in India werd uitgevonden. De Indiase koning die het spel te zien kreeg, was er zo enthousiast over, dat hij de uitvinder aanbood om elke beloning te vragen die hij maar wilde. De uitvinder vroeg het volgende: één rijstkorrel voor het eerste veld van het schaakbord, twee rijstkorrels voor het tweede, vier voor het derde, acht voor het vierde, enzovoort - tot het vierenzestigste en laatste veld bereikt zou zijn. De koning stemde lachend in met een schijnbaar zo eenvoudige beloning.

In dit artikel:

Afbeelding 1. Een schaakbord.Hoeveel rijstkorrels moet de koning in totaal betalen als hij er voor het eerste veld 1 geeft, vor het tweede veld 2, voor het derde veld 4, enzovoort? Foto: KADUN-workshop.

Machtreeksen

Het lachen verging de koning al snel toen hij zijn geleerden liet uitrekenen hoeveel rijst hij de uitvinder zou moeten geven. Wie het geduld heeft om de berekening te doen zal ontdekken dat het gaat om ruim 18 triljoen rijstkorrels - 18.446.744.073.709.551.615, om precies te zijn. Ervan uitgaande dat een rijstkorrel zo'n 3 mm3 groot is komt dat neer op meer dan 50 kubieke kilometer aan rijst - genoeg om de hele (huidige) wereldbevolking zo'n twee eeuwen te voeden.

Had de koning dit antwoord kunnen voorspellen voor hij zou enthousiast akkoord ging met de eis van de uitvinder? Misschien niet exact, maar wie even over het probleem nadenkt, ziet al snel in dat de uitkomst inderdaad gigantisch moet zijn. Het blijkt zelfs niet al te lastig te zijn om het probleem iets algemener op te lossen. Wat als de uitvinder bijvoorbeeld gevraagd had op elk veld van het schaakbord het aantal rijstkorrels te verdrie- of verviervoudigen?

Laten we om te beginnen eens een nette wiskundige uitdrukking opschrijven voor het aantal rijstkorrels dat de koning dan moet betalen. In ons voorbeeld waarin dat aantal steeds met een factor twee toeneemt, is het totale aantal gelijk aan

1 + 2 + 22 + 23 + … + 263

Merk op dat de laatste term 263 is, en niet 264. Op het derde vakje liggen immers 2 × 2 korrels, op het vierde vakje 2 × 2 × 2 korrels, en op het laatste vakje dus 2 × … × 2 korrels met 63 factoren twee.

Voor het meer algemene geval kunnen we nu, zoals wiskundigen dat graag doen, de factor waarmee het aantal rijstkorrels steeds toeneemt x noemen. De uitkomst die we willen berekenen is dan

1 + x + x2 + x3 + … + x63

Dit is een eenvoudig voorbeeld van wat wiskundigen een machtreeks noemen: een som van termen waarin opeenvolgende machten van een variabele x voorkomen. Deze machtreeks is om twee redenen bijzonder:

  • Elke macht van x komt voor met een coëfficiënt die gelijk is aan 1. Een wat ingewikkelder machtreeks zou bijvoorbeeld de vorm 8 + 2x + 7x2 + 3x3 + … kunnen hebben.
  • Deze machtreeks heeft maar een eindig aantal termen: 64, om precies te zijn. In de wis- en natuurkunde komen ook (sterker nog: vooral) machtreeksen voor die een oneindig aantal termen hebben. Hoe we met dergelijke reeksen kunnen omgaan zullen we in een volgend artikel zien.

We hebben het probleem van de koning en het schaakbord nu dus op een nette wiskundige manier beschreven met behulp van een machtreeks. Maar helpt ons dat ook om het probleem op te lossen? En… waarom bespreken we dit probleem eigenlijk op een website over theoretische natuurkunde?

Afbeelding 2. Een schaal met rijst.Om deze schaal te vullen zijn de eerste 12 of 13 vakjes van het schaakbord voldoende.

Naar boven

De uitkomst van het probleem

Hoe berekenen we vanuit de machtreeks het aantal rijstkorrels dat de koning moet betalen? Er blijkt een grappige truc te zijn die het antwoord vrij eenvoudig geeft. Vermenigvuldig de uitdrukking (voor algemene groeifactor x) met (x-1). We vinden dan

(x-1) (1 + x + x2 + x3 + … + x63)
= x + x2 + … + x64 - 1 - x - x2 - … - x63

In deze berekening hebben we de haakjes uitgewerkt door eerst alle termen in de tweede factor met x te vermenigvuldigen, en vervolgens met -1. We zien dat in de uiteindelijke uitdrukking de term 'x' wegvalt tegen de term '-x', de term 'x2' tegen de term '-x2', enzovoort. Alleen de termen 'x64' en '-1' hebben geen partner, dus die termen blijven uiteindelijk over. Kortom: we vinden dat

(x-1) (1 + x + x2 + x3 + … + x63) = x64 - 1

Als we nu links en rechts de factor (x-1) wegdelen, vinden we een elegant eindantwoord voor onze machtreeks:

1 + x + x2 + x3 + … + x63 = (x64 - 1) / (x-1)

Invullen van de waarde voor x in ons oorspronkelijke probleem, x = 2, geeft nu bijvoorbeeld dat het totaal aantal rijstkorrels op het schaakbord gelijk moet zijn aan (264-1) / (2-1) = 264-1, en wie dat invult op een rekenmachine die met voldoende decimalen kan rekenen, vindt inderdaad het eindantwoord dat we aan het begin van dit artikel noemden. Had de uitvinder gevraagd om een toename met een factor 3 per veld, dan berekenen we nu even eenvoudig dat het totale aantal rijstkorrels dan

(364-1) / (3-1) = 1.716.841.910.146.256.242.328.924.544.640

zou zijn geweest - zo'n 1,7 quintiljard! Van een dergelijke hoeveelheid rijst zou de huidige wereldbevolking langer kunnen eten dan het heelal op dit moment bestaat.

Naar boven

Terzijde: een schatting van het antwoord

Overigens kunnen we er misschien niet van uitgaan dat onze arme koning exact weet hoe groot een getal als 264 is. Toch zou de heerser met een hoofdrekentrucje een heel aardige inschatting kunnen maken van het aantal rijstkorrels dat hij zou moeten betalen. Voor ons verhaal is die truc niet van belang, maar voor wie indruk wil maken op feestjes vermelden we het handigheidje hier toch.

Als we de verschillende machten van 2 op een rijtje zetten, komen we al snel een macht tegen die dicht bij een mooi, rond getal ligt: 210 is namelijk gelijk aan 1024, wat natuurlijk niet ver van 1000 af ligt. Dit is ook precies de reden dat in de informatica termen als 'kilobyte' gebruikt worden: het voorvoegsel kilo- betekent '1000', maar een kilobyte bevat 1024 enen en nullen.

Afbeelding 3. Computergeheugen.Computergeheugen wordt gemeten in kilo-, mega- en gigabytes. Een kilobyte bestaat uit 1024 enen en nullen, een megabyte uit 1024 x 1024, enzovoort. Foto: Wikipedia-gebruiker DrJolo.

Het getal 1000 bestaat uit drie factoren 10, dus tien factoren 2 komen grofweg overeen met drie factoren 10. Zestig factoren 2 komen dan grofweg overeen met zes maal drie, dus achttien factoren 10, en als we daar nog eens vier factoren twee aan toevoegen (24 = 16) ontdekken we dat 264 bij goede benadering gelijk is aan het getal 16 gevolgd door achttien nullen. Niet exact de juiste uitkomst (die begon met 18 gevolgd door nog achttien cijfers), maar voldoende dichtbij om de koning een idee te geven van de immense hoeveelheid rijst die hij nodig zou hebben.

Naar boven

Wat heeft dit allemaal met natuurkunde te maken?

In de natuurkunde is het zelden mogelijk om de uitkomst van een experiment exact te berekenen. Zelfs als we een wiskundig model hebben dat een experiment perfect beschrijft, blijkt de wiskunde vaak te lastig om meetuitkomsten precies te kunnen berekenen. Natuurkundigen maken daarom gebruik van allerlei benaderingsmethoden om meetuitkomsten zo nauwkeurig mogelijk te kunnen voorspellen.

Afbeelding 4. Richard Feynman.De natuurkundige Richard Feynman was een meester in het gebruik van storingsrekening. We zullen zijn naam later in dit dossier nog meerdere malen tegenkomen. Foto: Tamiko Thiel.

In deze reeks artikelen willen we de misschien wel meest gebruikte en interessantste van die methodes beschrijven: storingsrekening. Het idee van storingsrekening is om een meetuitkomst die we niet exact kunnen berekenen te benaderen met behulp van een machtreeks. Die machtreeksen lijken erg op het voorbeeld dat we hierboven in het verhaal van de koning en het schaakbord tegenkwamen, met het grote verschil dat - zoals we al kort noemden - zulke machtreeksen vaak oneindig veel termen bevatten. Hoe gaan we om met zulke oneindige optelsommen, en hoe kan het dat die gebruikt kunnen worden om een eindige meetuitkomst te berekenen? Dat bespreken we in het tweede artikel in dit dossier.

Naar boven

Het tweede artikel in dit dossier verschijnt op dinsdag 15 december.

Gepubliceerd: di, 08/12/2015 - 18:18