2
$\begingroup$

The question is how to calculate for the general problem.

The specific problem is this:

Given a door code of $n$ numbers on a 10 digit panel, how many combinations do you have to try?

The catch is that the mechanism that senses whether the correct code has been entered has no concept of the start and end of the code. So the sequence 123456 is actually testing 3 unique door codes - my particular case uses a 4 digit code.

The question is, given this modification how many combinations are there given a code length of $n$?

In answer to the comment:

Yes, I am looking for the shortest sequence of digits that tests all combinations.

  • 0
    if you add that comment as an answer i will mark it correct.2010-12-07

1 Answers 1

5

Consider a directed graph whose nodes are all possible strings of $n-1$ digits, and with 10 edges labelled 0, ..., 9 going out from each node; the edge $x$ from node $abc\dots de$ leads to $bc\dots dex$, and should be thought of as "testing the code $abc \dots dex$". The first $n-1$ digits that you enter put you in an initial state, and for each subsequent digit you follow the corresponding edge to another state.

In your example, you start in state 123, and move through states 234, 345, 456.

Since the in- and out-degree of each node is equal (=10), you can find an Eulerian circuit that passes every edge exactly once; that is, there is a sequence of length $(n-1)+10^n$ which tests all the $10^n$ codes in the shortest way imaginable (each code is tried exactly once).

  • 0
    @John: Well, perhaps not a lot har$d$er, but this kind of error does disrupt the re$a$ding, since one has to spell it out loud to figure out what is meant (as opposed to just recognizing the word $b$y looking). N$a$tive English speakers are pro$b$ably more likely to make such "phonetic" mistakes; another common example is confusing "there/their/they're", which I would never do, since the corresponding phrases in Swedish are completely different. (But I probably make many other mistakes that sound very strange to a native speaker!)2011-07-25