A safe usually suggests a long list of separate attempts. But if the lock keeps checking only the last few digits typed, one continuous sequence can hide every possible code inside it. This is the idea behind de Bruijn sequences: arranging combinations so that they overlap with almost no waste.
The door that opens by itself
Riddle statement
A safe uses a 4-digit code, from 0000 to 9999.
You may type a sequence of digits as long as you like, one digit after another. The safe opens as soon as the last four digits typed match the correct code.
What is the shortest sequence that is guaranteed to open the safe, no matter what the code is?
Show solution
Solution
Answer: the minimum is 10003 digits.
The key idea is overlap. If you type, for example,
you have not tested just one code. You have tested every block of four consecutive digits inside it:
Every new digit, after the first three, creates one new possible code.
There are 10000 possible codes, from 0000 to 9999. So a sequence that is guaranteed to open the safe must contain all 10000 blocks of 4 digits.
Now we get the lower bound. A sequence of length $L$ has exactly $L - 3$ positions where a block of 4 digits can begin. Therefore, even if no block were ever repeated, we would need:
So:
No sequence shorter than 10003 digits can guarantee that the safe will open.
It remains to see why 10003 digits are enough. This is the delicate part.
Start with a tiny version. Suppose the lock used only the symbols 0 and 1, and the code had length 2. The possible codes would be:
The sequence
contains all of them as consecutive blocks of length 2:
We did not write the codes separately. We overlapped them.
The real safe works the same way, only on a larger scale.
Think of every possible ending of three digits as a station. For example, 314 is a station. If you are at station 314 and type a 7, you have just tested the code 3147 and moved to station 147:
So every 4-digit code is a path from one 3-digit station to another.
From each station, there are exactly 10 paths leaving it, one for each digit you might type next. And into each station, there are exactly 10 paths entering it, one for each possible previous digit.
Moreover, all the stations are connected: from any three-digit ending, you can reach any other one by typing its three digits. Since every station has as many incoming paths as outgoing ones, there is a closed route that uses every path exactly once.
Reading the digits along that route gives a circular sequence containing every possible 4-digit code exactly once.
That circular sequence has 10000 digits. To turn it into a normal linear sequence, we write those 10000 digits and then repeat the first 3 digits at the end, so that we do not lose the blocks that crossed the closing point of the circle:
The lower bound and the construction match, so the exact minimum is:
The safe opens not because we try codes faster, but because each new digit reuses the three digits before it.