{"id":1972,"date":"2014-05-06T18:00:53","date_gmt":"2014-05-06T15:00:53","guid":{"rendered":"http:\/\/spektrum.fi\/spektraklet\/?p=1972"},"modified":"2018-03-15T15:53:34","modified_gmt":"2018-03-15T12:53:34","slug":"dorrkodsproblemet","status":"publish","type":"post","link":"https:\/\/spektrum.fi\/spektraklet\/dorrkodsproblemet\/","title":{"rendered":"D\u00f6rrkodsproblemet"},"content":{"rendered":"

En skr\u00e4mmande tanke<\/strong><\/p>\n

F\u00f6rest\u00e4ll dig f\u00f6ljande scenario: Du \u00e4r p\u00e5 v\u00e4g till \u00e5rhundradets fest som f\u00f6rst\u00e5s ordnas i Majstranden. D\u00e5 du sitter p\u00e5 bussen m\u00e4rker du att du har gl\u00f6mt telefonen hemma, men du l\u00e5ter inte en s\u00e5dan liten motg\u00e5ng s\u00e4nka hum\u00f6ret. N\u00e4r du \u00e4ntligen anl\u00e4nder till Majstranden och skall sl\u00e5 in d\u00f6rrkoden m\u00e4rker du att du inte kommer ih\u00e5g den! ”Inget problem”, t\u00e4nker du, f\u00f6r n\u00e5gon m\u00e5ste ju snart komma ut och s\u00e5 kan du slinka in samtidigt. Efter att ingen setts till p\u00e5 en kvart fattar du pl\u00f6tsligt att alla andra redan m\u00e5ste vara p\u00e5 festen (det \u00e4r ju \u00e5rhundradets fest vi talar om), s\u00e5 det \u00e4r klart att ingen \u00e4r p\u00e5 v\u00e4g ut p\u00e5 l\u00e4nge!<\/p>\n

”Ingen orsak att panikera”, t\u00e4nker du, ”detta problem g\u00e5r nog att l\u00f6sa”. Du samlar ihop allt vad du vet om problemet: koden \u00e4r fyra siffror l\u00e5ng (f\u00f6r alla koder \u00e4r ju det), och fr\u00e5n manicken du sl\u00e5r in den p\u00e5 ser du att den kan best\u00e5 av siffror fr\u00e5n 0 till 9. Du ber\u00e4knar snabbt att det finns totalt 10^4 = 10000 m\u00f6jliga koder, s\u00e5 ifall du pr\u00f6var dem alla, m\u00e5ste d\u00f6rren \u00f6ppnas f\u00f6rr eller senare. F\u00f6r inmatandet av alla koder m\u00e5ste du d\u00e5 sl\u00e5 in 4 \\cdot 10000 = 40000 siffror.<\/p>\n

\"D\u00f6rrkod\"<\/p>\n

Hmm…1234 kanske?<\/p>\n

Efter att du funderat p\u00e5 problemet en stund till, s\u00e5 kommer n\u00e5gon och \u00f6ppnar d\u00f6rren<\/del> du ih\u00e5g att n\u00e5gon sagt \u00e5t dig att d\u00f6rrkodsl\u00e4sare brukar fungera lite konstigt. De kr\u00e4ver n\u00e4mligen inte att man h\u00e5ller en paus efter att man slagit in de fyra siffrorna f\u00f6rr\u00e4n den kollar ifall koden \u00e4r korrekt. F\u00f6r att d\u00f6rren skall \u00f6ppnas r\u00e4cker det att man i n\u00e5got skede sl\u00e5r in de fyra korrekta siffrorna i rad. Det har allts\u00e5 ingen skillnad fast man matar in felaktiga siffror i b\u00f6rjan s\u00e5 l\u00e4nge den korrekta koden sl\u00e5s in i n\u00e5got skede. Ifall du sl\u00e5r in fem siffror har du allts\u00e5 matat in tv\u00e5 olika fyrsiffriga koder! Den f\u00f6rsta best\u00e5r av siffrorna 1-4, och den andra av siffrorna 2-5.<\/p>\n

Du fattar direkt att f\u00f6r att alla koder skall finnas n\u00e5gonstans i den sekvens du sl\u00e5r in, m\u00e5ste du knappast mata in 40000 siffror, eftersom koderna \u00f6verlappar varandra. Vilken strategi skulle det l\u00f6na sig att anv\u00e4nda f\u00f6r att f\u00e5 inslaget alla koder med s\u00e5 f\u00e5 siffror som m\u00f6jligt? Naturligtvis l\u00f6nar det sig att undvika upprepning av koder, allts\u00e5 vill du i varje skede sl\u00e5 in en s\u00e5dan siffra som skapar en fyrsiffrig kod som du inte matat in tidigare.<\/p>\n

Simplifikation av problemet<\/strong><\/p>\n

F\u00f6r att simplifiera problemet rycker vi oss f\u00f6r en stund bort fr\u00e5n v\u00e5rat scenario och funderar i st\u00e4llet p\u00e5 en d\u00f6rrkodsl\u00e4sare som endast har siffrorna 0 och 1 och kr\u00e4ver en tv\u00e5siffrig kod. Det finns allts\u00e5 2^2 = 4 olika koder, n\u00e4mligen koderna 00, 01, 10 och 11. I vilken ordning skulle man sl\u00e5 in siffror i detta fall f\u00f6r att med s\u00e5 liten m\u00f6da som m\u00f6jligt f\u00e5 upp d\u00f6rren? En m\u00f6jlighet \u00e4r att sl\u00e5 in sekvensen 11001. Den inneh\u00e5ller alla koder:<\/p>\n