There is a safe with a 4-digit code (0000 to 9999).
You can type a long sequence of digits. The box opens as soon as the last 4 digits entered match the code.
How many digits do you need to type at least to guarantee opening, without knowing the code?
Home > Riddles > The door that opens by itself
The door that opens by itself
Hints
Show hints
- Lower bound: a string of length $L$ contains at most $L-3$ distinct substrings of length 4. To cover the 10000 codes: $L-3\ge 10000 \Rightarrow L\ge 10003$.
- Upper bound (construction): There exists a De Bruijn sequence $B(10,4)$, cyclic, of length 10000, containing each 4-digit block exactly once.
- By linearizing it and adding the first 3 digits to the end, you get a string of length $10000+3=10003$ that covers all 4-digit codes.
Solution
Show full solution
Back to problem
Answer: minimum 10003 digits.
Lower level:
A string of length $L$ contains at most $L-3$ distinct substrings of length 4.
To cover the 10000 codes:
$$ L-3\ge 10000\Rightarrow L\ge 10003. $$
Upper level (construction):
There is a De Bruijn sequence $B(10,4)$, cyclic, of length 10000, containing each 4-digit block exactly once.
By linearizing it and adding the first 3 digits at the end, you get a string of:
$$ 10000+3=10003 $$
which covers all 4-digit codes.
Since the lower and upper bounds coincide, the exact minimum is 10003.
Related riddles
Keep practicing
If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.