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.

up vote 8 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!)

  • That is exactly what I was looking for! Thanks – MichalisN Mar 6 '12 at 20:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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