22
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 26
    $\begingroup$ 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] $\endgroup$
    – Milo P
    Commented May 29, 2015 at 15:54
  • $\begingroup$ Not sure about "laziness" - the actual rule sounds if anything harder to program than the original requirement! (But i'm nitpicking, +1 from me) $\endgroup$
    – IanF1
    Commented Jun 29, 2015 at 5:35

2 Answers 2

Reset to default
25
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ 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 $\endgroup$
    – Compass
    Commented May 29, 2015 at 18:21
-1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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