Puzzle: Cracking the safe

Question

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode.

For instance, if I enter the stream $012345$, I am trying each of the combinations $0123$, $1234$, and $2345$.

Clearly, a 40000-length string $000000010002...9999$ is guaranteed to crack the safe.

Can we try each of the 10000 combinations using a shorter string? What's the shortest string we can devise to try every combination?

Answer 1

The object you are interested in is called a De Bruijn graph. Construct a graph where each node is one 4-digit sequence. Then put a directed edge from $a$ to $b$ if the last $3$ digits of $a$ are the same as the first $3$ digits of $b$.

See: http://en.wikipedia.org/wiki/De_Bruijn_graph

A directed Hamiltonian path will tell you what sequence to enter the digits (to try all possible combinations as fast as possible). These graphs always have such a path. So then, the fewest times you would have to push the button is $4$ (for the first code) and then $1$ more button push for each remaining possibility for a total of $1(4)+9999(1)=10003$ button pushes.

Answer 2

You can do it with $10,003$ letters, and I believe that this is the shortest possible string. We start by creating a De Bruijn sequence of the $4$ letter words over the alphabet $\{0,1,\dots,9\}$. What this is is a cyclic sequence (meaning that when you get to the end, you start reading from the beginning again) which contains every possible $4$ letter word exactly once.

Let's look at a shorter example for clarity: consider binary words of length $3$. Then I claim that $$ 00010111 $$ is a De Bruijn cycle for these words, as reading left to right we get $$ 000,001,010,101,011,111,110,100. $$ Note that between $111$ and $110$ we started reading back at the beginning of the sequence as it is a cycle.

What De Bruijn showed was that, given any alphabet $A$, one can always create such a cycle for $n$ letter words over $A$. If we think of it as a cycle, then this will have length $|A|^n$, as each letter starts a unique $n$ letter word.

Going back to your problem, we can create a De Bruijn cycle for all $4$ letter strings over $\{0,1,\dots,9\}$. This will have length $10,000$, but we cannot enter a cycle into the machine, we have to enter a string. So repeating the first three letters at the end of our sequence will give us a universal string of length $10,003$.