‘Geachte heer, mevrouw, wij organiseren een running dinner, waarbij deelnemers verschillende gangen op verschillende locaties koken en eten. We zitten al dagen te puzzelen op een schema voor wie wanneer waar eet, zodat iedereen elkaar spreekt. We komen er niet uit, kunt u ons helpen?’ Dat was ongeveer de strekking van een e-mail die binnenkwam bij Platform Wiskunde Nederland, waar ik werk. Ik stuurde hem door, zodat hij tenslotte terecht kwam bij Cor Hurkens van de TU Eindhoven. Die mailde binnen een dag een overzichtelijke tabel met wie wanneer waar moest eten. Het probleem bleek een variant van het zogenaamde Oberwolfach-probleem.
Het Oberwolfach-probleem werd in 1967 geformuleerd tijdens een wiskundeconferentie in het Duitse plaatsje Oberwolfach. Het oorspronkelijke vraagstuk luidt bijna hetzelfde als de vraag uit de e-mail: n deelnemers gaan x verschillende gangen eten op s verschillende locaties. Hoe moeten ze ingedeeld worden zodat iedereen een keer naast elkaar zit? Het verschil tussen de vraagstukken is dat het in het Oberwolfach-probleem niet alleen de bedoeling is met iedereen een keer aan tafel te zitten, maar zelfs iedereen een keer als directe buurman te hebben.
Zo’n probleem kan worden aangepakt met behulp van methodes uit de grafentheorie, een belangrijke tak van de wiskunde. Men geeft dan de situatie weer als een netwerk van punten en lijnen: een graaf. Het uitgangspunt is een graaf met n punten die de verschillende deelnemers voorstellen. Er lopen lijnen van elk punt naar elk ander punt, omdat alle deelnemers elkaar kennen en met elkaar aan tafel geplaatst kunnen worden. U kunt zich misschien al wel voorstellen dat er variaties op het vraagstuk zijn waarbij niet iedereen naast elkaar mag of wil zitten. Een versie is bijvoorbeeld het Emily Post-probleem, waarbij mannen en vrouwen om en om aan tafel geplaatst moeten worden.
Uitgaande van zo’n graaf waarin alle deelnemers worden weergegeven, wordt gezocht naar een opdeling van deze graaf in kleinere grafen, die de tafelschikkingen voorstellen. Elk punt stelt dan opnieuw een deelnemer voor, en een lijn geeft aan dat de deelnemers naast elkaar aan tafel zitten. De kleinere grafen zullen cirkelvormig zijn, omdat elke deelnemer precies één linkerbuur en één rechterbuur heeft. Voor elke gang moet opnieuw zo’n opdeling gemaakt worden, waarbij de moeilijkheid ligt in het aanbrengen van voldoende afwisseling zodat iedereen een keer naast iedereen heeft gezeten.
Nu is het natuurlijk niet zo dat wiskundigen hun tijd doorbrengen met het berekenen van tafelschikkingen voor running dinners, al willen ze wel eens een verzoeknummer doen, zo is gebleken. De vragen die onderzoekers over dit probleem stellen, zijn dieper van aard. Hoeveel gangen moeten er bijvoorbeeld zijn om te zorgen dat n deelnemers ook echt een keer naast ieder ander kunnen zitten? En is er een vaste methode te verzinnen waarmee dit aantal gangen en de bijbehorende tafelschikkingen in elke situatie berekend kan worden?
Wiskundigen gebruiken grafen om allerlei typen netwerken weer te geven, zoals spoorwegnetwerken, telefoonverbindingen en het internet. De huidige dienstregeling van de NS is bijvoorbeeld ontwikkeld door professor Lex Schrijver met behulp van grafentheorie. Dat maakt bovenstaand vraagstuk groter dan alleen de situatie aan de eettafel. Maar onderzoekers houden ook gewoon van een beetje puzzelen, en bedachten al doende allerlei varianten op het Oberwolfach-probleem. Er is bijvoorbeeld ook een ‘echtgenoot-ontwijkende’ variant. Een aantal getrouwde stellen organiseert gezamenlijk verschillende diners, en het is uitdrukkelijk de bedoeling is dat niemand naast de eigen echtgenoot zit.
27.08.2019
11:00
Ik zou dit schema ook erg graag ontvangen. Ik organiseer voor een aantal netwerken al een aantal jaren zulke diners, maar het is elke keer een drama om een goed schema te maken.
Alvast bedankt dus!
11.01.2019
19:35
Het is inderdaad een tijd geleden, maar ook ik zou het schema heel erg graag ontvangen.
24.03.2017
11:17
Beste …
Waar kan ik een schema vinden of excel programma om een running dinner te organiseren.
vr gr Kees Jansen
05.03.2015
09:40
@Annie, ik heb geen tabel voor je helaas, maar je zou eens contact op kunnen nemen met Cor Hurkens, zie http://www.win.tue.nl/~wscor/
03.03.2015
15:39
Speuren op t web brengt me op deze pagina: is het schema nog beschikbaar? Zo ja dan ontvang ik graag deze invultabel, zou me jaarlijks een hoop moeite kunnen besparen.
26.02.2015
21:17
na veel zoeken eindelijk iemand gevonden en de stoute schoenen aangetrokken om maar gewoon te vragen. Het is weliswaar lang geleden maar zou je mij ook het invultabel kunnen sturen. Ik kom er niet uit
alvast bedankt.
06.01.2015
22:41
Beste Marieke, Maud,
Hier hetzelfde puzzelprobleem. Werkte de tabel? Zouden jullie deze dan ook willen doorsturen naar mij?
Vriendelijk dank.
12.04.2013
22:33
En maud is het gelukt met de tabel? zou je hem ook naar mij kunnen mailen? mvg marieke
27.03.2013
15:28
@Maud: de tabel heb ik niet, maar je zou even een mailtje kunnen sturen naar evgeny[at]math.leidenuniv.nl. Leg dan even uit dat het gaat om een vraagstuk dat al eens eerder door Platform Wiskunde is opgelost. Hij kan je vast verder helpen.
16.03.2013
14:53
Als deze tabel nog beschikbaar is, zou ik deze graag doorgestuurd krijgen want wij organiseren ook een running dinner. Alvast bedankt!
15.02.2012
16:04
Heren en Dames van het Wiskunde platform, bedankt!
Dankzij jullie gepuzzel een top avond gehad.
14.02.2012
22:45
En het klopte ook nog! Ik heb met iedereen aan tafel gezeten. Top prestatie voor wiskunde platform en erg leuk dat de Tafelronde Zaltbommel zo de pers haalt!:)