19
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Watch the related video by James Grime here and read about De Brujin Sequences. $\endgroup$
    – JMoravitz
    Jun 10 '15 at 18:34
  • $\begingroup$ Nice pictures and explanations for De Bruijn Sequences. For instance, $B(2,4)$, a shortest string containing all passwords of length four over the alphabet $\{0,1\}$ is 0000100110101111. $\endgroup$
    – Pål GD
    Jun 10 '15 at 21:58
  • $\begingroup$ After reading more about De Brujin sequences, I can add they can be generated in linear time by concatenating the periodic reductions of all Lyndon words generated by the FKM algorithm (as described in Frank Ruskey's Combinatorial Generation). Definitely a surprise! $\endgroup$
    – scip
    Jun 23 '15 at 8:50
13
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ On a side note, I think these things pop up frequently in bio-informatics in terms of gene sequencing. $\endgroup$
    – TravisJ
    Jun 10 '15 at 18:34
  • 2
    $\begingroup$ Yes they do! They also generalize to something called universal cycles, which is a generalization to other combinatorial objects, such as permutations or encodings of subsets of a set. $\endgroup$
    – TomGrubb
    Jun 10 '15 at 18:37
  • 2
    $\begingroup$ Here's a sequence of length 10,003 containing all four digit passwords: $B(10,4)$ $\endgroup$
    – Pål GD
    Jun 10 '15 at 22:04
  • $\begingroup$ Isnt there som1ething like this that remains unsolved? Some conjecture about 1!+2!+3!+...n!? $\endgroup$ Jun 10 '15 at 22:22
9
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ (+1) very clear. The last paragraph made the whole thing click with me. $\endgroup$
    – Karl
    Jun 10 '15 at 20:42

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