Hoe verdeel je een taart onder een grote groep mensen? Lees mee hoe wiskunde je hier bij helpt!
Laatst was ik jarig en werd ik 30. Hoewel ik er in eerste instantie nogal tegenop zag, besloot ik het uiteindelijk toch te vieren. Jarig word je immers sowieso, dan kan je er maar beter iets leuks van maken. Ik besloot mijn eeuwige wens in vervulling te laten brengen; veel versiering en een uitbundige taart stonden bovenaan mijn verlanglijstje.
Uitbundige taart
De wens kwam uit en ik kreeg een prachtige, gigantische en overdreven versierde taart. Helaas deed zich direct een volgend probleem voor: hoe ging ik deze taart in stukken verdelen en al mijn gasten tevreden maken met hun stuk? Dit was immers geen gewone taart; de bovenkant was bedekt met verschillende soorten snoepgoed, letters, glitters, kleuren, toefjes van room en suiker, noem het maar op. Al gauw bleek dat mijn tien gasten hun eigen voorkeur hadden voor een bepaald deel van de taart. Simpelweg de taart in tien even grote stukken verdelen en onder de gasten willekeurig verdelen, zou waarschijnlijk wat teleurgestelde gezichten opleveren. Dat wilde ik natuurlijk niet op mijn feestje!
Gelukkig kwam aan mijn ontreddering snel een eind, ik kende namelijk de Banach-Knaster Last-Diminisher-procedure, vernoemd naar de Poolse wiskundigen Stefan Banach (1892-1945) en Bronisław Knaster (1893-1980), die de procedure hebben bedacht.
Ik kreeg een prachtige, gigantische en overdreven versierde taart, maar hoe ging ik 'm eerlijk verdelen?
FreepikSnijden en kiezen
Je kent wellicht wat de Cut and Choose-procedure heet, voor het verdelen van een taart (of iets anders lekkers!) onder twee mensen: de ene persoon snijdt, en de ander kiest een stuk. Dat is een manier om te zorgen dat allebei de mensen een stuk krijgen dat zij als minstens 1/2 van de taart waarderen. Let op: dit hoeft dus niet de helft van de taart te zijn in grootte, het gaat hier echt om de subjectieve waardering van de spelers. De Banach-Knaster Last-Diminisher-procedure is vergelijkbaar, maar werkt voor willekeurig grote groepen.
De procedure kent een aantal eenvoudige vereisten/aannamen. Een eerste aanname is dat alle n gasten een waardering bedenken over verschillende onderdelen van de taart. Bijvoorbeeld: Alice geeft de chocoladetopping een 8, maar de zuremattentopping een 2, terwijl Bob deze allebei een 5 geeft en dus even lekker vindt. De chocolade is voor Alice dus meer waard dan voor Bob. Wanneer Alice een stuk met chocoladetopping krijgt, zal zij met een kleiner stuk tevreden zijn dan Bob. Charlie geeft de chocoladetopping een 0. Hoe groot het stuk met chocoladetopping ook is dat Charlie krijgt, Charlie zal nooit ook maar een beetje tevreden zijn.
Een tweede belangrijke vereiste is dat de gasten tijdens de procedure niet meer van hun waardering afwijken; de procedure kan verandering van mening niet accomoderen. Een derde vereiste is dat waarderingen additief (optelbaar) zijn: verdubbeling van een stuk maakt het twee keer zo veel waard. Een vierde aanname is dat ieder in het eigen belang handelt en de waarde van diens eigen stuk taart wil maximaliseren.
Ik verdeelde mijn taart via de Banach-Knaster Last-Diminisher-procedure
FreepikBanach-Knaster-procedure
Nu gaat de procedure als volgt: We nummeren de gasten en zetten ze op volgorde neer. In mijn voorbeeld zijn 10 gasten, maar dit kan elk eindig aantal zijn. In het geval van een algemeen ongespecificeerd aantal, gebruiken we in de wiskunde vaak letters. Stel nu dus dat er n gasten zijn. Het is dan eerlijk als iedereen een stuk krijgt, dat naar hun mening 1/n-e van de taart waard is. Bijvoorbeeld: bij twee personen gun je beiden de helft van de taart. Als de notatie met n lastig voor te stellen is, kan je voor de rest van de omschrijving n = 10 invullen voor jezelf.
We geven de taart met een mes aan gast nummer 1. Die mag een stuk afsnijden dat volgens hun eigen waardering 1/n-e (1/10-e) van de taart waard is. Het afgesneden stuk wordt samen met het mes doorgegeven aan persoon 2. Die bedenkt: ‘vind ik dit stuk meer waard dan 1/n-e van de taart?’ Als dat zo is, snijdt persoon 2 een stuk extra af van het stuk, zodat het overgebleven stuk wel 1/n-e van de taart waard is volgens het oordeel van persoon 2. Als dat niet zo is, dan laat persoon 2 het stuk taart onaangetast. Het stuk taart en het mes gaan dan door naar persoon 3, en die krijgt dezelfde opgave: afsnijden of doorgeven. Op deze manier gaan we door tot persoon n. De laatste persoon die van het stuk heeft gesneden, krijgt het stuk en verlaat de procedure. Dan beginnen we opnieuw bij persoon 1 (als persoon 1 nog onbedeeld is), ditmaal met de taart waar al een stuk uit verdwenen is. Na elke ronde verdwijnt er een stuk taart. We gaan verder tot er één persoon over is, die het laatste stuk krijgt.
Hoe zorg je ervoor dat iedereen blij is met zijn of haar stuk taart?
FreepikNu vraag je je wellicht af: wat als de eerste persoon een veel groter stuk afsnijdt? Wanneer je in eigen belang handelt, waarom zou je dan eerlijk zijn? Wel nu, oneerlijk zijn is juist riskant: wanneer je een stuk afsnijdt dat voor jou meer waard is dan 1/n-de van de taart, dan loop je het risico dat iemand anders met het stuk eindigt, terwijl dat voor jou nog steeds meer waard is dan 1/n-e van de taart. In dat geval blijft er dan na de eerste ronde minder dan 1-1/n = (n-1)/n van de taart over, en heb je jezelf tekort gedaan. Het is dus voor jezelf altijd beter om eerlijk te zijn.
Enorme puinhoop
Een andere belangrijke vraag is: kunnen we met deze procedure garanderen dat iedereen een stuk krijgt dat zij zelf als minstens 1/n waarderen? We noemen dit een proportionele verdeling van de taart. Het antwoord is: ja, dat kan. Immers, wanneer je een stuk uitkiest, is dat altijd 1/n-e van de taart waard. De laatste persoon krijgt ook minstens 1/n-e van de taart, want alles wat diegene niet had gekozen, was maximaal (n-1)*(1/n) = (n-1)/n waard, en dan blijft er dus minstens 1/n-e over.
Een laatste opmerking voor praktisch nut: deze procedure zoals nu uitgelegd, veroorzaakt een enorme puinhoop. Je kunt dit natuurlijk ook op papier doen, en daarna de echte taart netjes snijden. Mijn tip is dus: zet bovenaan je verlanglijstje ‘een uitbundige taart’, nodig al je familie en vrienden uit, en spelen maar!