Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
    
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 –  John Nicholas Dec 7 '10 at 11:24
    
@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.] –  Hans Lundmark Dec 7 '10 at 12:12
    
[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".) –  Hans Lundmark Dec 7 '10 at 12:13
    
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 ;) –  John Nicholas Dec 9 '10 at 9:54
    
@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. ;-) –  Hans Lundmark Dec 9 '10 at 11:23
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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