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

  • 23
    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
up vote 23 down vote accepted

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.

  • 3
    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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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