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.

  • 1
    $\begingroup$ What do you mean by "how many combinations"? Are you looking for the shortest sequence of digits that tests all possible codes? $\endgroup$ Dec 7 '10 at 9:55
  • 2
    $\begingroup$ You may want to take a look at the de-Bruijn sequence at: en.wikipedia.org/wiki/De_Bruijn_sequence $\endgroup$
    – user3533
    Dec 7 '10 at 9:58
  • $\begingroup$ if you add that comment as an answer i will mark it correct. $\endgroup$ 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.

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

  • $\begingroup$ I should of said, I have not studied maths since a physics degree in 2000. Unfortunatley i am not sure how to interpret and use what you have said let alone verify it. Sorry $\endgroup$ Dec 7 '10 at 11:24
  • $\begingroup$ @John: Try drawing (or imagining) this picture: write down all three-digit numbers 000, 001, 002, ..., 998, 999 and draw a circle around each. From the 000 circle you draw an arrow labelled "1" to to the 001 circle, an arrow "2" to the 002 circle, etc. And in general you draw an arrow "x" (for x=0,1,...,9) from each "abc" circle to the "bcx" circle. Then you start at 000 (for example) and try to follow the arrows around this mess in such a way that you use every arrow exactly once. Euler's theorem says it's possible. [Cont.] $\endgroup$ Dec 7 '10 at 12:12
  • $\begingroup$ [Cont.] As you walk along the arrows, you read off their labels, and that sequence of digits is what you should press (after the initial "000") in order to test all the codes as efficiently as possible. If you do the same construction with only the digits 0 and 1 (instead of 0 to 9), you get the figure on the Wikipedia page that user3533 pointed you to. I wasn't aware that it was called a de Bruijn sequence, so at least I've learned something new from your question. :-) (By the way, you should have said, not "of said".) $\endgroup$ Dec 7 '10 at 12:13
  • $\begingroup$ That makes a lot of sense. Thankyou. As an aside, I gave up on grammer the day the americans started saying 'winningest'. Anyway I don't think there is one form of a language that is the 'correct' form - it evolves. As long as I can question and understand your gist i am happy as we can then get to the real meaning. But yeah, you're right ;) $\endgroup$ Dec 9 '10 at 9:54
  • $\begingroup$ @John: Sorry about the off-topic grammar remark. I can't resist doing that sometimes. Regardless of grammar and spelling, it was probably easier for me to understand what you meant than the other way around. ;-) $\endgroup$ Dec 9 '10 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.