You're standing outside your apartment building after a late night out, with perhaps one beer too many, and you realize you have completely forgotten the code to get in. Luckily, you're a mathematical genius, and somehow that part of the brain is completely unaffected by the alcohol, so you decide to find the optimal strategy to get in.
The code is entered on a standard 0-9 keypad, and you know that it is a four digit code. Entering the correct sequence of digits will open the door. When entering a sequence, every four digit sub sequence will be evaluated by the security system. I.e. entering 195638 will evaluate the following three sequences: 1956, 9563, and 5638, so it is a waste of time to try each four digit sequence one by one.
Question: What is the smallest number of keypresses needed to try every sequence between 0000 and 9999?
Answer
The De Bruijn sequence $B(k,n)$ is a cyclic sequence over an alphabet of size $k$ that contains every possible word of length $n$ exactly once; see the wikipedia for more information.
The length of such a De Bruijn sequence $B(k,n)$ is $k^n$, that is, it equals the number of words of length $n$ over an alphabet of size $k$.
The De Bruijn sequence $B(10,4)$ is over an alphabet of size 10 (that is, the ten digits 0,1,2,$\ldots$,9), and it contains every possible word of length 4 (that is, every 4-digit number). The length of $B(10,4)$ is $10^4$.
The puzzle now does not ask about a cyclic sequence, but about an ordinary linear sequence. If we follow the cyclic De Bruijn sequence $B(10,4)$ around the cycle, we will encounter every 4-digit number exactly once. This takes $10^4$ digits plus an additional 3 digits at the end (where the cycle closes, while the linear sequence remains open).
Hence the answer is $10^4+3=10003$ keypresses.
No comments:
Post a Comment