# Combinations: security code with no defined start and finish

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$?

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

• What do you mean by "how many combinations"? Are you looking for the shortest sequence of digits that tests all possible codes? Dec 7 '10 at 9:55
• You may want to take a look at the de-Bruijn sequence at: en.wikipedia.org/wiki/De_Bruijn_sequence Dec 7 '10 at 9:58
• if you add that comment as an answer i will mark it correct. Dec 7 '10 at 11:24

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.
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).