En skrämmande tanke

Föreställ dig följande scenario: Du är på väg till århundradets fest som förstås ordnas i Majstranden. Då du sitter på bussen märker du att du har glömt telefonen hemma, men du låter inte en sådan liten motgång sänka humöret. När du äntligen anländer till Majstranden och skall slå in dörrkoden märker du att du inte kommer ihåg den! ”Inget problem”, tänker du, för någon måste ju snart komma ut och så kan du slinka in samtidigt. Efter att ingen setts till på en kvart fattar du plötsligt att alla andra redan måste vara på festen (det är ju århundradets fest vi talar om), så det är klart att ingen är på väg ut på länge!

”Ingen orsak att panikera”, tänker du, ”detta problem går nog att lösa”. Du samlar ihop allt vad du vet om problemet: koden är fyra siffror lång (för alla koder är ju det), och från manicken du slår in den på ser du att den kan bestå av siffror från 0 till 9. Du beräknar snabbt att det finns totalt möjliga koder, så ifall du prövar dem alla, måste dörren öppnas förr eller senare. För inmatandet av alla koder måste du då slå in siffror.

Hmm…1234 kanske?

Efter att du funderat på problemet en stund till, så kommer någon och öppnar dörren du ihåg att någon sagt åt dig att dörrkodsläsare brukar fungera lite konstigt. De kräver nämligen inte att man håller en paus efter att man slagit in de fyra siffrorna förrän den kollar ifall koden är korrekt. För att dörren skall öppnas räcker det att man i något skede slår in de fyra korrekta siffrorna i rad. Det har alltså ingen skillnad fast man matar in felaktiga siffror i början så länge den korrekta koden slås in i något skede. Ifall du slår in fem siffror har du alltså matat in två olika fyrsiffriga koder! Den första består av siffrorna 1-4, och den andra av siffrorna 2-5.

Du fattar direkt att för att alla koder skall finnas någonstans i den sekvens du slår in, måste du knappast mata in 40000 siffror, eftersom koderna överlappar varandra. Vilken strategi skulle det löna sig att använda för att få inslaget alla koder med så få siffror som möjligt? Naturligtvis lönar det sig att undvika upprepning av koder, alltså vill du i varje skede slå in en sådan siffra som skapar en fyrsiffrig kod som du inte matat in tidigare.

Simplifikation av problemet

För att simplifiera problemet rycker vi oss för en stund bort från vårat scenario och funderar i stället på en dörrkodsläsare som endast har siffrorna 0 och 1 och kräver en tvåsiffrig kod. Det finns alltså olika koder, nämligen koderna , , och . I vilken ordning skulle man slå in siffror i detta fall för att med så liten möda som möjligt få upp dörren? En möjlighet är att slå in sekvensen . Den innehåller alla koder:

• 11001
• 11001
• 11001
• 11001

Är det möjligt att hitta en kortare sekvens som innehåller alla koder? Genom att analysera listan ovan ser vi fort att det inte kan gå. För att visa detta, antag att är en sekvens av siffror 0 och 1. Ifall den innehåller alla fyra olika koder av längd två, måste var och en av koderna starta vid olikt index i sekvensen. Därmed kan den sista koden starta som tidigast vid index 4, och eftersom den är av längden två, måste sekvensen vara minst fem siffror lång. Detta betyder att är sekvensen den kortaste möjliga lösningen. Dock finns det andra lösningar av längden fem också, t.ex. .

Dörrkodsläsare, modell datalog (Patent pending)

Hur skapades då sekvensen ? En möjlig strategi är följande: börja med den största koden (i detta fall ), och välj sedan den lägsta möjliga siffran som skapar en ny kod till sekvensen, dvs. en kod som inte från tidigare finns i sekvensen. Ifall detta alltid lyckas, kommer vi att få till stånd en möjligtvis kort sekvens, eftersom den inte upprepar några koder.

Ifall vi använder denna strategi i vårt ursprungliga scenario, kommer vi att få till stånd en sekvens av längden (börjandes med siffrorna ) som innehåller alla koder, en klar förbättring till att vara tvungen att mata in 40000 siffror!

Det allmänna problemet

Den stora frågan är följande: Kan vi för alla kodlängder och sifferantal (dvs. baser) alltid skapa en sekvens som inte upprepar någon kod två gånger? Svaret är kanske aningen överraskande ja. Beviset i sin helhet, till vilket det finns en länk i slutet av artikeln, är lite för invecklat för att tas upp i denna artikel, men det bygger på följande observation: Antag för enkelhetens skull att vi vill skapa koder av längd 4 som består av siffrorna 0, 1, 2 och 3. Ifall vi har någon kod, t.ex. , kan efter denna kod i sekvensen följa endast en kod som börjar med siffrorna och slutar med en av siffrorna 0, 1, 2 eller 3. Detta gör att sekvensen blir mycket symmetrisk, eftersom det efter någon av koderna endast kan följa någon av koderna .

Tillämpning till scenariot

Smart som du är kom du på denna lösning till problemet på säg…22 minuter. Du började sedan knacka in siffrorna, och eftersom du har ett utomordentligt minne kunde du hålla reda på vilka koder du redan slagit in. Efter en dryg timme lyckades du därmed få upp dörren, och kvällen var räddad. Snäll som du är skapade du åt dina vänner en textfil med den kod som behövs för att öppna vilken som helst dörr med fyrsiffrig kod i bas 10!

Till sist

Ett stort tack till Lasse och Jeremias för hjälpen med detta problem!

Den som är intresserad att läsa mera om dörrkodsproblemet kan ta en titt på följande text (på engelska):

The door code problem

Ifall du vill veta den sekvens (av längden 10003) som du säkert kommer in till Majstranden med, kan du skriva ut följande textfil:

Bas 10, kodlängd 4