Netwerken met Sinterklaas

Die arme Sint moet ieder jaar weer heel Nederland doorreizen om alle cadeaus op tijd te bezorgen. Hoe doet hij dit toch?

28 november 2017

Hier in Parijs, waar ik een aantal maanden zit voor mijn onderzoek, zijn overal de kerstmarkten al begonnen en de kerstbomen al opgetuigd. Gelukkig heb ik een paar Nederlandse huisgenoten die pepernoten hebben meegebracht om toch nog wat Sinterklaas te vieren. Genoeg tijd dus om aan de wiskundige problemen van Sinterklaas te denken!

Wat is de snelste route voor Sinterklaas?
Pixabay CC0

Het is een hele opgave om op één avond cadeautjes door het hele land te rond te brengen. Daarom neemt de Sint hiervoor het liefst de kortste route door Nederland. Je kunt dit zien als een probleem op een netwerk: de locaties van de cadeautjes zijn de punten, en de lijnen tussen twee punten geven de reistijd tussen de locaties van de cadeautjes aan. Hieronder zie je een klein voorbeeld hiervan, waar Sint vier cadeautjes moet bezorgen, en daarna weer teruggaat naar zijn stoomboot.

Een netwerk van vier cadeautjes. De rode lijnen geven de snelste manier om alle cadeautjes te bezorgen.
Clara Stegehuis voor NEMO Kennislink

Een hoop routes

Stel dat Sinterklaas in plaats van vier pakjes n pakjes moet bezorgen in verschillende steden. Hoeveel verschillende volgorden bestaan er om al die pakjes te bezorgen? Als startpunt kan de Sint alle n verschillende steden kiezen. Daarna zijn er nog n-1 steden over waar hij het tweede pakje kan gaan bezorgen. Als je hiermee doorrekent, kun je beredeneren dat er in totaal n x(n-1)x(n-2)x…x1=n! verschillende manieren zijn om alle pakjes te bezorgen. Van al die n! verschillende routes wil de Sint graag de kortste route hebben. Als Sint in 20 verschillende steden pakjes bezorgt, betekent dit dus dat er 2.432.902.008.176.640.000 verschillende routes zijn die hij kan nemen!

Prijsvraag

De lengte van al deze routes doorreken is dus geen optie. Wiskundigen zijn al jaren op zoek naar een meer efficiënte manier om de snelste route te vinden, en noemen dit het handelsreizigersprobleem. Dit probleem is een stuk jonger dan Sinterklaas zelf, het werd voor het eerst rond 1800 gedefinieerd. Sindsdien zijn er allerlei wiskundige trucs bedacht om niet alle mogelijke routes te hoeven door te rekenen.

Toch heeft nog niemand een echt snelle manier bedacht om voor een groot aantal steden de beste pakjesbezorgroute te vinden. We weten eigenlijk niet eens of een snelle manier überhaupt bestaat. Diegene die een efficiënte methode vindt om grote pakjesbezorgroutes te maken, of laat zien dat deze niet bestaat, krijgt zelfs een prijs van een miljoen dollar!

Advies voor Sinterklaas

Hieronder zie je de beste route die Sint kan nemen om pakjes te bezorgen in 20 verschillende steden. We zien dat Sint beter niet de Afsluitdijk kan nemen om naar Leeuwarden te gaan en in plaats daarvan een uitstapje door de polder maakt. Ook moet hij een aantal keer omdraaien om dezelfde route als de heenweg te nemen. Hopelijk helpt dit de Sint om zo veel mogelijk pakjes op die ene avond te bezorgen!

Reageer