# Fastest way to try all passwords

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.

-
–  TMM Mar 6 '12 at 19:35
@TMM: Why not add that as an answer? –  Aryabhata Mar 6 '12 at 19:39

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.