Puzzle: Cracking the safe 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?
 A: 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$. 
A: 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.
