Fastest way to try all passwords

Question

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.

Answer 1

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