Archive for March 15, 2017
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 105 possible codes, so entering all of them sequentially would require 5 × 105 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.
- 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.