Smarta tjuven
En tjuv står utanför en port med en fyrsiffrig portkod. Om han skriver in en sekvens med fyra rätta siffror i rad (0-9) så öppnas porten. Vad är den kortaste sekvens med siffror tjuven kan skriva in för att täcka in alla portkoder, från 0000 till 9999?
Bump
Samma problem har faktiskt redan varit uppe som kluring förut:
https://www.pluggakuten.se/trad/knacka-ett-kodlas-utan-ok-knapp/
Man kan tänka så här.
Vi tänker oss en graf med tusen noder, numrerade 000 till 999. Från nod a till nod b går det en riktad kant om de två sista siffrorna i a är de samma som de två första i b. Då är:
1) Grafen sammanhängande, man kan ta sig från (abc) till (def) via (bcd)-(cde)-(def).
2) Alla noder han indegree 10 och outdegree 10.
Villkor 1 & 2 ger att grafen innehåller en eulerkrets, dvs det finns en vandring i grafen som använder varje kant exakt en gång. Nu kan vi tänka på varje kant som en fyrsiffrig kod dvs kanten mellan (abc) och (bcd) är koden (abcd).
Så vi trycker först 3 siffror, säg 000, och sedan trycker vi hela tiden den siffra som tar oss till nästa nod i eulercykeln. Efter 10000 knapptryckningar har vi passerat varje kant exakt en gång och följaktligen tryckt varje fyrsiffrig kod exakt en gång. Så 10003 knapptryckningar räcker. Att mindre än 10003 inte går är uppenbart.
