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.

Suppose you have a computer with a password of length $k$ in an alphabet of $n$ letters. You can write an arbitrarly long word and the computer will try all the subwords of $k$ consecutive letters. What is the smallest word that contains all combinations of $k$ letters as subword? (i.e. the fastest way to hack the computer :) )

The smallest word that contains $n^k$ subwords of size $k$ has length $k-1^+n^k$ and based on some easy cases, we would like to prove that it is in fact possible to find a word of such length that contains all possible passwords. The problem can be translated into a problem in graph theory, by taking as vertices all words of length $k$.

We tried $k=2$, where you can prove the conjecture by induction. For $n=2$ and small $k$ it also works.

share|improve this question
4  
See De Bruijn sequence and De Bruijn graph –  TMM Mar 6 '12 at 19:35
    
@TMM: Why not add that as an answer? –  Aryabhata Mar 6 '12 at 19:39
add comment

1 Answer

up vote 6 down vote accepted

What you are looking for is the De Bruijn sequence and the associated graph, the De Bruijn graph.

Hamilton paths in the De Bruijn graph correspond to De Bruijn sequences. Hamilton paths in the De Bruijn graph of words of length $k$ also correspond to Euler tours in the De Bruijn graph of words of length $k - 1$, and since all De Bruijn graphs are regular, the existence of such sequences for each alphabet size $n$ and word length $k$ follows.

(A few years ago I stumbled upon these graphs for my thesis, so I can provide more fascinating properties of these graphs if needed!)

share|improve this answer
    
That is exactly what I was looking for! Thanks –  Michalis Mar 6 '12 at 20:06
add comment

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.