Wiskundemeisjes

Wat er bijzonder is aan 0000111101100101000

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.