Hoe vijf muffins tot een diep wiskundig vraagstuk leidden

Wiskunde

Hoe verdeel je vijf muffins eerlijk onder drie studenten, terwijl het kleinste stuk zo groot mogelijk is? Dit negen jaar oude raadsel is uitgegroeid tot een veel breder wiskundig vraagstuk over verdelingen.

Stel, je hebt vijf muffins, die je moet verdelen over drie studenten. Kun je de muffins zó snijden dat het kleinste stuk groter dan 5/12 is? Foto iStock

Op een koude woensdag in maart van dit jaar bezocht Alan Frank een voordracht van wiskundige William Gasarch op het Massachusetts Institute of Technology (MIT). Frank, werkzaam als software-ontwikkelaar en liefhebber van wiskunderaadsels, had een doos muffins meegebracht om uit te delen. Daar had hij een reden voor, want Frank is de bedenker van het zogeheten muffinprobleem, het onderwerp van de voordracht waarvoor Frank speciaal was gekomen.

Je moet vijf muffins onder drie studenten verdelen. Hoe doe je dat, als ze allemaal even veel moeten krijgen? De simpelste oplossing is om elke student één hele muffin te geven, van elk van de overige muffins een derde af te snijden en elke student nog twee derde muffin te geven. Maar kan het ook anders? Bestaat er een snijmethode waarbij het kleinste muffinstuk groter dan een derde is? Dat is Franks muffinprobleem.

Zo’n methode is er inderdaad: deel één muffin in twee gelijke helften en de andere muffins in porties van vijf twaalfde en zeven twaalfde. Twee studenten krijgen ieder een halve muffin en twee stukken van grootte 7/12, de derde krijgt vier stukken van grootte 5/12. Het kleinste stuk, van grootte 5/12, is groter dan 1/3, het kleinste stuk bij de eerste snijmethode.

Kan het nog beter? Kun je de muffins zó snijden dat het kleinste stuk groter dan 5/12 is? Nee. Het bewijs hiervan staat in de illustratie.

Puzzelrubriek

Dit specifieke muffinprobleem werd in 2009 door Frank bedacht. Vier jaar later verscheen het in de puzzelrubriek in The New York Times. Dat opende de deur naar het algemene muffinprobleem, een diep wiskundig vraagstuk waar William Gasarch, een 58-jarige wiskundige van de University of Maryland, de afgelopen jaren veel tijd in heeft gestoken. Met een aantal collega’s en studenten schreef Gasarch er een 200 pagina’s tellend artikel over en hij sprak erover bij diverse gelegenheden: naast zijn optreden op het MIT was hij onder meer te gast bij conferenties in San Diego, Atlanta en La Maddalena, ten noorden van Sardinië.

Bij het algemene muffinprobleem is het aantal muffins en het aantal studenten niet vastgesteld op vijf en drie. Die aantallen kunnen willekeurige getallen zijn; Gasarch geeft ze aan met de letters m (van muffin) en s (van student). Het doel is om de m muffins zó te snijden en te verdelen, dat elk van de s studenten even veel krijgt en waarbij het kleinste stuk niet kleiner is dan strikt noodzakelijk – kruimels willen de studenten niet. Bestaat er een formule waarmee je de maximale grootte van het kleinste stuk kunt berekenen?

Graphic Roland Blokhuizen/NRC

Zo’n algemene formule hebben Gasarch en zijn collega’s vooralsnog niet gevonden, maar ze hebben wel deelresultaten geboekt. Bijvoorbeeld: als het aantal muffins groter is dan het aantal studenten, is het kleinste stuk in elk geval niet kleiner dan 1/3. Kruimelwerk wordt de verdeelpartij dus nooit.

Dankzij een indrukwekkend staaltje rekenen zijn tientallen speciale gevallen succesvol onderzocht. Elk geval waarbij het aantal muffins niet groter is dan 70 en het aantal studenten niet groter is dan 60, is opgelost. Bijvoorbeeld: met 24 muffins en 11 studenten heeft het kleinste stuk grootte 19/44.

Verder is het gelukt om formules te vinden (en te bewijzen) voor sommige situaties waarbij het aantal studenten vast ligt en het aantal muffins variabel is. Zijn er bijvoorbeeld drie studenten en is het aantal muffins ‘een drietal plus één’, is de optimale grootte van het kleinste stuk (m–2)/(2m–2). Is het aantal muffins ‘een drietal plus twee’, heeft het kleinste stuk grootte m/(2m+2).

Altijd een rationaal getal

Los van de formules hebben de wetenschappers een paar theoretische vragen kunnen beantwoorden. Bijvoorbeeld: de optimale grootte van het kleinste stuk is altijd een rationaal getal, dat wil zeggen: een breuk waarvan teller en noemer geheel zijn, dus geen getallen zoals de vierkantswortel uit 2 of de logaritme van 7. Vooralsnog is het onduidelijk of er een efficiënt algoritme bestaat om die optimale grootte te berekenen.

Wat de wiskundigen ook nog niet zeker weten, maar wel vermoeden, is dat de optimale grootte van het kleinste stuk niet van de afzonderlijke getallen m en s afhangt, maar slechts van de verhouding tussen die twee getallen. Met andere woorden: de oplossing van het probleem met 48 muffins en 22 studenten, of 480 muffins en 220 studenten, is niet anders dan de oplossing van het probleem met 24 muffins en 11 studenten, omdat 48/22 en 480/220 beide gelijk zijn aan 24/11. Het lijkt Gasarch erg onwaarschijnlijk dat dit vermoeden fout is, maar een hard bewijs heeft hij er niet voor.

Het muffinprobleem laat zien dat de lijn tussen serieuze wiskunde en raadsels die onder de noemer ‘recreatieve wiskunde’ vallen, erg dun is. Gasarch licht per e-mail toe: „Onze resultaten hebben we gevonden dankzij stellingen uit de gemengde geheeltallige programmering.” Dat is een deelgebied van de wiskundige optimalisatie, dat sinds 1950 een turbulente ontwikkeling heeft doorgemaakt en buiten de wiskunde toepassingen vond in onder meer de economie en de biologie. Een denkbare toepassing van het muffinprobleem zou het optimaal verdelen van stukken land kunnen zijn.

Correctie 18-9: In een eerdere versie van dit artikel stond dat William Gasarch 68 jaar oud was. Dat klopt niet, hij is 58 jaar oud.

    • Alex van den Brandhof