Wiskundemeisjes

Van telefoonbeantwoorders en deurcodes

Laatst kwam mijn oud-huisgenoot Ernst met een wiskundig probleem. Jaren geleden wilde hij een telefoonbeantwoorder kraken (om nobele redenen natuurlijk). Om het apparaat van een afstand te bedienen moest je een viercijferige code intoetsen. Maar, je hoefde geen enter te geven na die vier cijfers. Dus als de juiste code 1729 was, dan kwam je in het syteem als je 1729 intoetste, maar ook als je 111111729 intoetste of 172717281729 probeerde. Ernst vroeg zich af of er een slimme manier bestaat om alle mogelijke codes achter elkaar te proberen. Hoeveel toetsen moet je indrukken om 0000, 0001, 0002 en zo door tot en met 9999 te proberen? Met domweg alle combinaties achter elkaar proberen heb je 40.000 toetsen nodig. Ernst dacht dat je veel kon winnen door slimme overlappingen te kiezen.

Ik wilde dit leuke probleem zelf oplossen, om aan Ernst te bewijzen hoe nuttig wiskunde is in het dagelijks leven in het algemeen en bij het kraken van telefoonbeantwoorders in het bijzonder. Samen met mijn kamergenoot Sierk begon ik eens met codes van twee cijfers in het binaire stelsel, want we wilden het onszelf niet gelijk té moeilijk maken. In dit geval zijn de mogelijke codes 00, 01, 10, 11. Die kan je in een reeks van vijf cijfers allemaal testen, met 00110 bijvoorbeeld.

Ook voor alles codes van drie cijfers (000, 001, 010, 011, 100, 101, 110 en 111) kwamen we snel tot een mooie korte reeks:

0001110100.

We zagen wel dat korter niet ging, elk getal (behalve de eindcijfers) wordt in drie codes gebruikt. De vetgedrukte 1 zit bijvoorbeeld in 001, 011 en 111.

Maar toen zaten we vast. Een mooie reeks voor alles codes van vier cijfers was lastiger te vinden. En voor het echte probleem met viercijferige codes bestaande uit 1, 2, 3, 4, 5, 6, 7, 8, 9 en 0 zagen we zo snel helemaal geen oplossing.

Zweedse hulptroepen
Het werd toch wel lastig om de vraag van Ernst even snel te beantwoorden - ons eigen onderzoek moest ook doorgaan. Maar hoera voor google! Ik vond de weblog van Stefan Geens. Deze Zweedse journalist stelde precies dezelfde vraag als Ernst. Al ging het bij hem niet om telefoonbeantwoorders, maar om een appartementencomplex in Oslo dat codes in plaats van sleutels gebruikte. Hij stelde zich voor dat je midden in de nacht door de sneeuw naar huis liep en als je dan ein-de-lijk bij je appartement was, je de code niet meer wist. Hoeveel toetsen moet je dan met je verkleumde vingers indrukken om binnen te komen?
Geens werkt op deze pagina prachtig naar het algemene antwoord toe. Hij begint net als wij met simpele reeksen 0-en en 1-en, loopt op een gegeven moment vast, maar komt dan terecht op de juiste wiskundige pagina's en uiteindelijk duikelt hij zelfs allerlei recente publicaties op over dit onderwerp. Het antwoord is dat je om alle combinaties van vier cijfers te proberen je maar 10.003 toetsen hoeft in te drukken. Dat betekent dat je (op de drie begincijfers na) elk getal in deze reeks in vier codes tegelijk probeert. Zo'n reeks heeft een mooie regelmaat, om maar eens een stukje te nemen:

...4639 4739 4839 4939 5439 5539 5639 5739 5839 5939 6439 6539 6639 6739 6839...

Deze reeksen getallen heetten De Bruijn reeksen en er is veel meer over te vertellen. Maar dat doet Geens zo goed, dat ik suggereeer dat je nu snel op bovenstaande link klikt.

(Ionica)

p.s. Toen ik dit probleem een paar dagen later aan mijn promotor vertelde, had hij voor ik klaar was met vertellen al een boek over De Bruijn reeksen uit de kast getrokken.