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?


The answer is to use a de Bruijn sequence, as discussed in response to this question on CS Theory. This gives a sequence of length $10^4=10\,000$. However, the sequence is cyclic, in the sense that if you wrote it on a paper tape and joined the ends together to form a loop, only then would it contain every possible 4-digit sequence and some of those sequences would cross the join. So, for a linear sequence, you need to repeat the first three items at the end, giving $10\,003$, improving on the obvious solution of length $40\,000$.

(Thanks to PålGD for pointing out the issue with cyclicity.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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