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.

Deze column verscheen vandaag in de Volkskrant.

Mijn vriendin Cristel studeerde geschiedenis met als specialisatie achttiende-eeuwse dagboeken. Op feestjes belandt ze steevast naast iemand die werkelijk alles weet van de Peloponnesische oorlog. Als zo iemand hoort dat zij een historica is, dan verwacht hij dat ze daar uren met hem over kan praten. Cristel vindt het dan altijd een beetje gênant om toe te moeten geven dat zij helemaal niets weet van de Peloponnesische oorlog.

Als wiskundige kom je bijna nooit in zulke situaties, omdat de meeste mensen bij wiskunde niet verder komen dan de stelling van Pythagoras. Daarom was ik zo verbaasd toen iemand laatst op een borrel aan me vroeg hoe het zat met het vermoeden van Collatz.

Ik wist gelukkig wel wat het vermoeden van Collatz was. Het gaat over reeksen getallen. Je begint met een willekeurig geheel getal, groter dan nul. Als het getal even is, dan deel je het door twee. Als het getal oneven is, dan vermenigvuldig je het met drie en tel je er één bij op. Daarna herhaal je dit proces met de uitkomst, en opnieuw, en opnieuw.

Bijvoorbeeld:

6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

of

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.

Het resultaat als je begint bij 6, 9 of 42.

Je stopt bij één, omdat je vanaf daar in een vicieuze cirkel belandt: één gaat immers naar vier en dan via twee weer terug naar één. Het vermoeden van Collatz is dat je altijd op één uitkomt, met welk getal je ook begint.

Probeer het zelf maar eens voor je lievelingsgetal. Als je getal kleiner is dan 10^18 dan kom je zeker op één uit, tot die grens is het vermoeden met de computer getest. Het aantal stappen kan behoorlijk groot worden: als je begint met een bescheiden 27 heb je bijvoorbeeld al 112 stappen nodig voor je bij 1 eindigt.

De meeste wiskundigen denken dat het vermoeden van Collatz waar is en dat je inderdaad voor elk getal bij één zult eindigen. Maar niemand heeft een bewijs. De in 1996 overleden wiskundige Paul Erdös verzuchtte volgens de overlevering dat de wiskunde nog niet klaar was voor dit soort moeilijke problemen. Voor de zekerheid loofde hij toch maar 500 dollar uit voor een oplossing. Die oplossing is er nog steeds niet.

Dit alles vertelde ik op de borrel. De getallenvoorbeelden zocht ik snel op met mijn telefoon, iets wat ik ook van harte aanraad bij lastige vragen over Peloponnesische oorlogen. De vragensteller keek me wat teleurgesteld aan. Dus dit kunnen wiskundigen níet oplossen? Wat zitten jullie dan de hele dag achter jullie bureaus te doen? En wat kunnen jullie wel?

Het is misschien gênant om een vraag te krijgen over een onderwerp waarvan je nog nooit hebt gehoord. Maar het is nog veel gênanter om toe te moeten geven dat jij en je vakgenoten een ogenschijnlijk eenvoudig probleem niet kunnen oplossen.