## Codes, Keypads, and Sequences

*March 15, 2017 at 7:29 am* *
2 comments *

When my colleague Chris Meador says, “I’ve thought of a math problem,” rest assured that I’ll spend a good portion of that workday trying to find a solution instead of tackling the items on my to-do list.

Last week, he emailed me the following:

My garage door opener has an exterior keypad that allows me to open the door by entering a 5‑digit number. There is no ENTER key, so the keypad “listens” for the correct code and disregards a false start. How many key presses would it take to test every possible code?

Theoretically, there are 10^{5} possible codes, so entering all of them sequentially would require 5 × 10^{5} key presses. However — because the keypad ignores false starts — some key presses can be saved. For example, typing 123456 will actually test two codes, 12345 and 23456.

Chris continued by asking:

Is it possible to construct an optimal string of key presses of minimal length that tests every possible code?

And with that, my Tuesday was ruined.

I had seen this problem before, or at least a version of it. The top four students at the MathCounts National Competition compete in a special event called the Masters Round, and one year the problem was about something called **D Sequences**. The author used this nickname because such sequences of minimal length are known as *de Bruijn sequences*, after the mathematician Nicolas Govert de Bruijn who proved a conjecture about the number of binary sequences in 1946.

Luckily for Chris, he caught a nasty viral infection last week, which gave him plenty of time to lie in bed thinking about the problem. He emailed me on Monday to inform me of his progress:

I did not manage to prove anything, but I did write a computer program that generates sequences using a pretty straightforward algorithm, and I was able to confirm that solutions are possible for 2‑, 3‑, 4‑, and 5‑digit codes.

That note reminded me that the best way to ensure a happy life is to surround yourself with intelligent people who share similar interests. Chris concluded his email to me with this:

I’d say [that my garage] is pretty secure, since it would take me about 14 hours to punch in all the possible numbers, reading from a list.

Feel free to read more about **de Bruijn sequences** at MathWorld, but you might want to try the following problems first.

- Construct a de Bruijn sequence that contains every two-digit permutation of 0’s and 1’s.
- Construct a de Bruijn sequence that contains every three-character permutation from an alphabet with three characters.
- What is the minimum length of a string of letters that would contain every possible five-letter “word,” that is, every possible permutation of 5 letters, using the Latin alphabet?

Counting things is something that mathematicians, especially those studying combinatorics, do quite often. Yet how they count can be atypical:

When asked how many legs a sheep has, the mathematician replied, “I see two legs in front, two in back, two on the left, and two on the right. That’s eight total, but I counted every leg twice, so the answer is four.”

And there you have it.

Entry filed under: Uncategorized. Tags: code, combination, de Bruijn, garage, keypad, permutation, sequence.

## 2 Comments Add your own

### Leave a Reply to venneblock Cancel reply

Trackback this post | Subscribe to the comments via RSS Feed

1.BLAN | April 24, 2017 at 3:45 pmWhat about the fact that people tend to not choose totally random 5-digit codes, and instead chose things that are easier to remember like 12345 or 42017? That could be used to modify the testing script so that it prioritizes these common codes which could greatly reduce the amount of time it takes to crack.

2.venneblock | April 24, 2017 at 4:29 pmFair point. I’ll have to ask Chris for confirmation… he seemed to imply that the system came pre-loaded with a 5-digit passcode, and he didn’t have the option of setting it himself. But if that’s the case, then your theory would apply in reverse — I suspect that any pre-loaded passcode would avoid numbers like 12345 or 66666, thus also reducing the number of permutations to check.