Aanpak Vaatwasser vullen

Terug naar het vullen van de vaatwasser. Pi wil elk stuk vaat maar één keer een plaatsje geven. Dat wil zeggen, reeds geplaatste vaat wordt niet meer verplaatst. En bovendien wil Pi dat zodanig doen dat op ieder moment de vaat redelijk goed verdeeld is over de hele vaatwasser. Wat het lastiger maakt is dat je bij het plaatsen van een stuk vaat niet weet welke dingen er later mogelijk nog bij komen.

Een vaatwasser is een driedimensionaal apparaat en elk stuk vaat is een driedimensionaal voorwerp dat een grillige vorm kan hebben. Dit maakt nadenken over geschikte methodes om vaat te plaatsen moeilijk. Daarom probeert Pi het probleem eerst te vereenvoudigen.

Vat elk stuk vaat op als een punt, en de vaatwasser als een eenheidskubus. Hoe kun je achtereenvolgens punten in een kubus plaatsen zodanig dat de geplaatste punten altijd redelijk goed verdeeld zijn? Dat lijkt ook nog knap moeilijk. Daarom gaat Pi het nog eenvoudiger maken: plaats punten achtereenvolgens in een eenheidsvierkant. Dan is het nog maar een tweedimensionaal probleem. Ook dit blijkt nog lastig.

Op aandringen van Phi, maar duidelijk met enige tegenzin, besluit Pi om de stap te maken naar één dimensie: plaats punten achtereenvolgens in het eenheidsinterval, zodanig dat ze altijd redelijk goed zijn verdeeld. Als je van tevoren weet hoeveel punten je moet plaatsen, dan is het makkelijk. Je kunt die punten namelijk precies gelijkelijk verdelen. Alleen rijst wel de vraag hoe het zit met de randen. Daar kun je misschien ook beter vandaan blijven, omdat het water dan niet zo makkelijk aan alle kanten komt.

De ultieme vereenvoudiging is om de vaatwasser op te vatten als een cirkel, door het eenheidsinterval rond te sluiten. Dan zijn er geen randen meer (daar moeten we later maar rekening mee zien te houden). Nu luidt de vraag dus hoe je het beste achtereenvolgens punten op een cirkel kan zetten zodanig dat ze altijd redelijk goed verdeeld zijn. Het eerste punt plaatsen is triviaal, want vanwege de symmetrie van de cirkel staat het overal "hetzelfde". Maar het tweede punt vergt al een afweging. Zet je het precies tegenover het eerste punt dan is dat optimaal als er niets meer bijkomt. Maar zodra een derde punt geplaatst moet worden krijg je daar spijt van en had het tweede punt beter ergens anders kunnen staan.