Puzzle: Cracking the safe [duplicate]

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

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