Wiskundemeisjes

Deze column staat vandaag in de Volkskrant.

Vorige maand overleed de Nederlandse wiskundige N.G. de Bruijn. Ik ontdekte zijn speelse wiskunde jaren geleden toen een vriend mijn hulp vroeg bij het kraken van een code. Hij wilde als grap de boodschap op iemands telefoonbeantwoorder veranderen. Zijn slachtoffer had een destijds hypermodern apparaat dat je vanaf elke telefoon op afstand kon bedienen, mits je de geheime viercijferige code invoerde. Je mocht daarbij net zoveel getallen intoetsen als je wilde. Dus als de juiste code 4567 was, dan kwam je met 1234567 of 4444567 in het systeem. Mijn vriend vroeg zich af wat de snelste manier was om de10.000 mogelijke codes te proberen. Domweg alle mogelijkheden achter elkaar intoetsen gaf een reeks van 40.000 cijfers. Wist ik een wiskundige truc om het sneller te doen?

Ik begon eerst met een eenvoudiger probleem: een zo kort mogelijke rij zoeken met alle viercijferige codes van alleen enen en nullen. In dat geval zijn er zestien verschillende mogelijkheden, en alle mogelijkheden na elkaar proberen geeft dan een reeks van 64 cijfers. Maar ik zag al snel dat het sneller kan doordat codes elkaar mogen overlappen. Toets bijvoorbeeld 000011 en je probeert met zes cijfers meteen drie codes: 0000, 0001 en 0011.

Als je die overlap optimaal gebruikt, dan zit elk cijfer dat je intoetst in vier verschillende combinaties, behalve de drie cijfers aan het begin en einde. In het beste geval zou je daarom zestien combinaties in negentien cijfers kunnen proppen. Na een tijdje prutsen op een envelop vond ik het volgende rijtje: 0000111101100101000. Liefhebbers mogen controleren dat in deze negentien cijfers inderdaad alle zestien mogelijke codes zitten.

Voor de telefoonbeantwoorder vermoedde ik dat op een zelfde manier alle tienduizend codes in slechts 10.003 cijfers moesten passen. Maar daar was met pen en papier geen beginnen aan. Toen wees een vriendelijke wiskundige me erop dat N.G. de Bruijn dit soort rijen al uitgebreid had geanalyseerd. Ze dragen nu zelfs zijn naam. De Bruijn bewees dat er altijd een rijtje bestaat waarin elke combinatie precies één keer voorkomt. Het maken van zo’n rij is nog best lastig, maar met wat programmeerwerk vond ik voor mijn vriend inderdaad een reeks van 10.003 cijfers met alle codes voor de telefoonbeantwoorder.

N.G. de Bruijn (die zelf trouwens bescheiden opmerkte dat hij niet de eerste was die een De Bruijn-rijtje beschreef.)

De Bruijn-rijen duiken op onverwachte plekken op. In het Sanskriet was er tweeduizend jaar geleden al één als ezelsbruggetje om namen te onthouden. Tegenwoordig zijn de rijtjes nuttig bij DNA-analyse en data-compressie. De mooiste toepassing - naast het kraken van die telefoonbeantwoorder- kwam ik laatst tegen in een goocheltruc. Je kunt er in een pak speelkaarten voor zorgen dat elke zes opeenvolgende kaarten een ander kleurenpatroon hebben (bijvoorbeeld zrzzrz, waar z een zwarte kaart is en r een rode). Een slimme goochelaar laat het dek couperen door een vrijwilliger, vraagt daarna zes mensen om steeds de bovenste kaart te pakken en laat degenen met een rode kaart hun hand opsteken. Uit die minimale informatie kan hij dankzij het unieke zwart-rood-patroon dan precies zeggen welke kaarten de vrijwilligers hebben. Jammer dat je deze truc alleen goed kunt uitvoeren als je net zo slim bent als N.G. de Bruijn.

In september ging ik naar het symposium ter ere van de 90ste verjaardag van N.G. de Bruijn. Hier schreef ik toen wat over hem.

Voor wie er niet naar toe kon: sinds kort staat een filmpje van de voordracht "Terugblik", die De Bruijn daar zelf gaf, online, net als de felicitatiebrieven die hij gebundeld van een boel bevriende collega's kreeg!

Donald Knuth begint zijn brief bijvoorbeeld met:

"I am so sorry that I forgot to send you a letter of congratulations on March 26, because that was the day on which you were exactly 32768 days old.

Soon you will be 90 years old, and that fact does have nontrivial interest from a linguistic standpoint, because of words like "nonagenarian". But I'm sure you agree that 2¹⁵ is a much more interesting number than 90. Alas, I missed my chance for that one. The best I can do now is to send this belated letter, to celebrate the 32869th day after your birth. (Not only is 32869 a prime, it's also the number of permutations of that do not contain the pattern 253 except in the context 42513, according to Claesson, Dukes, and Kitaev.)"

Op 9 juli is professor N.G. (Dick) de Bruijn 90 jaar geworden. Daarom vindt er op vrijdag 5 september aanstaande op de TU in Eindhoven een symposium plaats ter ere van hem en zijn bijdragen aan vele uiteenlopende takken van de wiskunde en informatica. De sprekers zijn Herman Geuvers (Radboud Universiteit Nijmegen en TU/e), Fairouz Kamareddine (Heriot-Watt University, Edinburgh, UK), Guido Janssen (Philips Research Laboratories), Jan van de Craats (Universiteit van Amsterdam) en N.G. (Dick) de Bruijn zelf. Op deze pagina is alle informatie over het symposium te vinden.

De Bruijn heeft een indrukwekkende publicatielijst op internet staan (zie hier en klik verder in de linkerbalk), en een groot deel van zijn artikelen zijn via deze link ook helemaal te lezen. Een zeer toegankelijke aanrader is zijn afscheidsrede uit 1984 (verschenen in het Nieuw Archief in 1985): Omzien in bewondering. Twee mooie citaten uit zijn rede staan hieronder. Het eerste gaat over het bewonderen van personen (p.106), het tweede over het bewonderen van stukjes wiskunde (p. 107).

Bij het bewonderen van personen schijnt een algemene regel te zijn dat wij bewonderen wat boven ons, maar niet te ver boven ons ligt. Het zo goed als onbereikbare wordt niet vaak bewonderd. Wij bewonderen meestal iets dat ons de illusie geeft dat wij er naartoe zouden kunnen groeien. Ik wil niet zeggen dat iedereen altijd zijn oordeel zo sterk door gedachten aan competitie laat beheersen, maar een vrij algemeen effect is het wèl. De man die in bad zingt kan denken dat het echt lijkt op wat de beroemde grote zangers voortbrengen, mits de badkamer voldoende galmt en mits de bader niet gehinderd wordt door muzikaal onderscheidingsvermogen. Desnoods zal hij door het onderduwen van een zeepbakje kunnen denken dat hij de opwaartse druk in vloeistoffen even goed had kunnen ontdekken als Archimedes. Maar dingen die ver boven zijn bevattingsvermogen liggen zal hij zelfs niet kunnen willen kunnen.

Als ik enige voorbeelden geef van bewonderenswaardige stukjes wiskunde dan zullen die op persoonlijke motieven gekozen zijn, in samenhang met eigen ontwikkelingsgeschiedenis en eigen tekortkomingen. Het zijn zaken van middelmatig grote omvang, met een harmonische opbouw. In enkele, maar lang niet in alle, worden vragen beantwoord die ik misschien wel zelf had kunnen stellen, soms aangepakt op een manier die ik misschien zelf had kunnen bedenken. Om te kunnen bewonderen stel ik me blijkbaar de eis dat er een duidelijke grondslag is en dat ik, van ieder punt uit, de weg naar de grondslag in zijn geheel kan overzien. Liefst moet ik het bij iedere hernieuwde kennismaking wéér mooi kunnen vinden, ook als de verwondering over verrassende wendingen reeds lang is vervaagd. Belangrijk is ook dat er een redelijk samenhangend complex van nieuwe begrippen wordt opgebouwd, maar dat over het geheel genomen de definitiedichtheid niet groot is.

Over welke bewonderde personen en stukjes wiskunde De Bruijn verder sprak, kun je in zijn rede lezen.