De wiskunde van bierauto's, veldproeven en geheime codes

Magische vierkanten, de driehoek van Pascal, het handelsreizigersprobleem: allemaal zijn het voorbeelden van discrete wiskunde. Een vakgebied met een frivole geschiedenis maar met serieuze toepassingen, aldus Nederlands discreet wiskundige van het eerste uur prof. J.H. van Lint.

In 1782 deed zich aan het hof van de Russische tsaar het volgende praktische probleem voor. Men wilde graag uit zes legerregimenten elk zes officieren uitnodigen, van iedere rang één. Vraag: is het mogelijk om deze 36 officieren in een vierkant op te stellen, zodanig dat in elke rij en iedere kolom elk regiment en iedere rang precies één keer voorkomen?

De legerleiding kwam er niet uit en legde het probleem voor aan Leonard Euler, een der grootste wiskundigen aller tijden, werkzaam in Sint Petersburg. Na enig gepuzzel zag Euler in dat het niet kon. Hij publiceerde zijn bevindingen in een internationaal vaktijdschrift, de Verhandelingen van het Zeeuwsch Genootschap van Wetenschappen Vlissingen (9, [1782], 85-239). Maar een bevredigende wiskundige analyse van het probleem vermocht zelfs de fameuze Euler niet te geven.

Tegenwoordig weten we dat dit "probleem van Euler', de constructie van een zogenaamd grieks-latijns vierkant van de orde 6, geen oplossing heeft maar dat het voor elke orde behalve 2 en 6 wel kan. Het bewijs hiervoor is een van de resultaten uit het deelgebied van de wiskunde dat traditioneel combinatoriek heet, maar tegenwoordig ook vaak schuilgaat achter het wat ruimere etiket discrete wiskunde.

""Discrete wiskunde gaat over het tellen van eindige verzamelingen. Dat lijkt makkelijk en dat is het ook zolang het om kleine verzamelingen gaat. Zo kun je, als je vier identieke eieren hebt en twee kleuren verf, laten we zeggen rood en blauw, via een tabelletje gemakkelijk achterhalen dat je de eieren op vijf verschillende manieren kunt verven: nul rood en vier blauw, een rood en drie blauw, enzovoorts tot aan vier rood en nul blauw. Maar als de getallen wat groter zijn, lukt die aanpak al snel niet meer. Bij tien eieren en vijf kleuren krijg je al 1001 verschillende manieren. Nog een paar stappen verder en het aantal mogelijkheden wordt zo astronomisch groot dat zelfs de computer er niet meer uitkomt.''

Aan het woord is prof.dr. J.H. van Lint, de nestor van de discrete wiskunde in Nederland en sinds twee jaar rector-magnificus van de TU Eindhoven. Het rectoraat vormt de niet geheel geambieerde bekroning van een lange en vruchtbare wetenschappelijke loopbaan. Al in 1959 werd Van Lint, die in Utrecht wiskunde had gestudeerd bij onder meer Hans Freudenthal en Frits van der Blij, benoemd tot hoogleraar aan de pas opgerichte TH Eindhoven. Hij werd daarmee in Nederland niet alleen de eerste hoogleraar met deze leeropdracht, maar ook, als 26-jarige, de jongste ooit benoemd. Tijdens een sabbatical van acht maanden bij Bell Labs in de Verenigde Staten in 1966 kwam Van Lint in aanraking met pionierswerk in de zogeheten coderingstheorie en andere takken van discrete wiskunde die juist sterk in opkomst begonnen te komen. Terug in Nederland gooide Van Lint het curriculum meteen drastisch om en stortte hij zich met verve op "discrete' problemen. De researchgroep in Eindhoven groeide uit tot een van de meest vooraanstaande in Europa.

Twee jaar geleden zei Van Lint, op aanbeveling van het college van dekanen van de TU, zijn vakgebied vaarwel en aanvaardde hij het ambt van rector-magnificus. Niet voor de gebruikelijke duur van drie jaar maar van vier, door het voortijdig aftreden van zijn voorganger naar aanleiding van de bestuurscrisis die was ontstaan in de nasleep van de Buck-Goudsmit affaire. Voor wiskunde zegt hij nu ""helaas nul komma nul tijd'' meer te hebben, en ook de gedachte om na vier jaar nog naar zijn vakgebied terug te keren wuift hij weg als een illusie. Des te leuker was het dat deze week de klok even was teruggedraaid: ter gelegenheid van zijn zestigste verjaardag eerden zijn collega's hem met een internationaal symposium over de discrete wiskunde en haar toepassingen.

I Ching

Zoals het probleem van Euler en dat van de eieren al aangeven, houdt de combinatoriek zich bezig met het rangschikken, selecteren, combineren dan wel permuteren van elementen van eindige verzamelingen. Het woord "discreet' geeft aan dat die elementen "heel' en stuk voor stuk aftelbaar zijn, of het nu gaat om officieren, eieren, getallen of putjes op een compact disk. Maar het vakgebied van de discrete wiskunde omvat meer dan combinatoriek in de enge zin: het strekt zich ook uit tot de elementaire getaltheorie, de waarschijnlijkheidsrekening, de cryptologie en de theorie van foutenverbeterende codes.

De geschiedenis van de discrete wiskunde reikt meer dan twee millennia terug. Zo komen er in de I Ching, een astrologisch boek van 2200 voor Christus, al magische vierkanten voor (getallenvierkanten waarin de rijen, kolommen en diagonalen alle dezelfde som hebben; geliefd voer voor getallenpuzzelaars). Een andere vroege bijdrage was de beschrijving van de "driehoek van Pascal' (de driehoekige rangschikking van binominaalcoëfficiënten) door de Perzische filosoof Nasr ad-Din al-Yusi in de dertiende eeuw (dus vier eeuwen vóór Blaise Pascal). In het Westen kwam de belangstelling voor discrete problemen in de wiskunde pas in de zeventiende eeuw goed op gang met het werk van Pascal en Pierre de Fermat.

Van Lint: ""Veel problemen uit de vroege geschiedenis van de discrete wiskunde hadden een wat frivole achtergrond. Ze kwamen voort uit grappige puzzeltjes en kregen van de wiskundigen alleen incidentele aandacht. Pas in de laatste halve eeuw is het vakgebied in een grote stroomversnelling gekomen en zie je ook serieuze toepassingen.''

Een eenvoudig voorbeeld van deze toepassingen is het ontwerp van veldproeven voor het uittesten van nieuwe graanrassen. Bij dergelijke proeven moet de invloed van de omgevingscondities zorgvuldig worden uitgesloten. Een van de mogelijkheden is, dat de vruchtbaarheid van het bouwland om wat voor reden dan ook in een bepaalde richting varieert. Om die invloed uit te sluiten kan men de n graanrassen inzaaien in een latijns vierkant van n bij n vakken, zodanig dat in elke rij en elke kolom juist één vak met dit ras voorkomt. De Britse geneticus Ronald A. Fisher introduceerde deze combinatorische aanpak al rond 1922 bij veldproeven op het landbouwkundig proefstation in Rothamsted. Tegenwoordig wordt de methode alom routinematig gebruikt.

Van Lint: ""Van zo'n vierkant van zeven bij zeven zijn alle permutaties al nauwelijks meer met de hand uit te schrijven. Je kunt dan natuurlijk overstappen naar de computer. Die komt daar makkelijk uit, en ook uit vierkanten van acht bij acht of van negen bij negen. Maar met vierkanten van tien bij tien of hoger neemt het aantal mogelijkheden zo snel toe, dat ook de supercomputer het niet meer aankan. Dan moet je het probleem toch echt met krachtiger middelen te lijf gaan - dat wil zeggen analytisch, met pen en papier.''

Bij die analytische aanpak stellen discrete wiskundigen zich in de praktijk twee soorten vragen. De eerste is: aan te tonen of een bepaalde permutatie of combinatie onder de gegeven omstandigheden wel of niet kan. De tweede soort is om, als het kan, ook te laten zien hoe. Dat laatste blijkt echter lang niet altijd mogelijk.

Van Lint: ""Het leuke van discrete wiskunde is de toepassingsgerichtheid. Je krijgt te maken met de meest uiteenlopende vraagstukken, die veelal direct voortkomen uit de praktijk. Een voorbeeld zijn de zogenaamde routeringsproblemen. Een oliemaatschappij zit met tankers die elk met hun eigen volume zo efficiënt en goedkoop mogelijk olie moeten aanvoeren naar een wereldwijd netwerk van klanten. Onnodig omvaren kost miljoenen en de problemen lopen al snel uit de hand wanneer je ze niet wiskundig aanpakt. De discrete theorie die daarbij wordt gebruikt heet combinatorische optimalisatie.''

Andere belangrijke toepassingen zijn er op het gebied van de cryptologie, de data-opslag en de foutenverbetering van compact-disks. Van Lint: ""In elke cd-speler zit een rekenapparaat dat fouten opspoort en verbetert met behulp van een correctiecode die op het schijfje is meegeprint. Van de informatie op een cd codeert maar driekwart voor muziek, het overige kwart bestaat uit codes gericht op het corrigeren van afleesfouten ten gevolge van krasjes en stofjes. De coderingstheorie die daaraan ten grondslag ligt, spruit direct voort uit de discrete wiskunde.''

Bierauto's

De vlucht die de discrete wiskunde de afgelopen decennia heeft genomen, begint tot uitdrukking te komen in het onderwijs. Met enig genoegen stelt Van Lint vast dat de discrete wiskunde de afgelopen jaren andere stukken uit het onderwijs is gaan verdringen. ""Er zijn hele stukken analytische wiskunde aan opgeofferd en de verwachting bestaat dat het ook deel zal uitmaken van een toekomstig nieuw wiskunde-B pakket. Terecht mijns inziens, want discrete wiskunde leent zich heel goed voor het aankweken van wiskundig inzicht.''

In het academisch onderwijs is de moderne discrete wiskunde allang zo ver ingeburgerd, dat op praktisch alle Nederlandse universiteiten ten minste één college over discrete wiskunde wordt gegeven. Van de afgestudeerden verdwijnt een deel in het bedrijfsleven, al constateert Van Lint dat veel grote firma's zich nog altijd nauwelijks van hun "discrete' problemen bewust zijn. ""Neem de routeringsproblemen waarmee elk groot bedrijf, van Albert Heijn tot Van Gend & Loos, te maken heeft. We hebben eens een student gehad die stage liep bij Heineken om daar de routerings-software onder de loupe te nemen. Ze gebruikten daar een standaardpakket en dat bleek van geen kant te deugen. Toen die student een veel beter routeringsschema voor de bierauto's had ontworpen, vroegen ze hem meteen om daar te blijven.''

Zelfs een industriegigant als Philips beseft nog niet zo lang ("minder dan tien jaar') hoezeer het discrete wiskundigen nodig heeft, zo constateert de Eindhovense rector die bij dat bedrijf nog steeds een adviseursfunctie bekleedt. Van Lint: ""Er zijn de laatste tijd überhaupt weinig wiskundigen meer op het Nat Lab en ik ben er van overtuigd dat ze dat op de lange duur opbreekt. Enfin, ze moeten het zelf weten, ik heb het ze vaak genoeg gezegd.''