Acme has released a brand new safe, secured with electronic 10-button keypad with the digits 0 through 9, with an X-length combination required to unlock. However, due to laziness, the keypad's programmer decides that, instead of requiring a new attempt each time, the safe will only consider the last $x$ button presses.

So, with $x=2$, if I were to press $1234$, the safe would evaluate whether $12$, $23$, and $34$ were valid combinations, while a traditional keypad safe would only evaluate $12$ and $34$.

For all values $x$, the worst case would be to try all combinations in serial, resulting in $10^x$ combinations of $x$ button presses, or $x \times 10^x$ presses. With $x=4$, we'd end up pressing this keypad up to $40,000$ times!

What is the best-case number of button presses to attempt all possible combinations for a combination of length $x$, and what is the list of button presses for $x=2$?

• Acme safes actually have a known vulnerability, which has been observed in certain limited contexts. To reproduce, get a coyote to accidentally drop one on its own head; the safe will then open, revealing the injured coyote's head within. [0 key press solution] – Milo P May 29 '15 at 15:54
• Not sure about "laziness" - the actual rule sounds if anything harder to program than the original requirement! (But i'm nitpicking, +1 from me) – IanF1 Jun 29 '15 at 5:35

The way to do it is

a De Bruijn sequence. Basically, it's a sequence $B(k,n)$ that contains all sequences of length $n$ made of $k$ different characters.

The number of keypresses for the length $x$ is

$10^x + (x - 1)$. A De Bruijn sequence is cyclic (end connects back to start) with length $k^n$, so we just need to add the starting $x - 1$ keypresses to the end.

The keypresses for $x = 2$ are

00102030405060708091121314151617181922324252627282933435363738394454647484955657585966768697787988990, as generated by the algorithm on Wikipedia.

• I thought this one up myself while half-asleep in bed, cool to know that there's already a huge mathematical text behind it XD – Compass May 29 '15 at 18:21

I originally encountered this as requiring a pattern that a human could execute without having to memorize a long sequence, even if it made the total number of numbers pressed longer. My solution to create an appropriate sequence was to use a Lucas-like sequence where $$F(n) = F(n-1) + F(n-2) + \cdots + F(n-x)$$

With various appropriately chosen seeds, this will create a set of loops that cover the space, which unfortunately must then be spliced together for optimal overage. The Frank Ruskey algorithm is much nicer in many ways.