## Posts tagged ‘combination’

### Codes, Keypads, and Sequences

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.

### Don’t Believe the HIPE

Let’s get this party started with a classic word puzzle.

What English word contains four consecutive letters that appear consecutively in the alphabet?

In *Mathematical Mind-Benders* (AK Peters, 2007), Peter Winkler describes how the puzzle above served as inspiration for a word game.

I and three other high-school juniors at a 1963 National Science Foundation summer program began to fire letter combinations at one another, asking for a word containing that combination… the most deadly combinations were three or four letters, as in GNT, PTC, THAC and HEMU. We named the game after one of our favorite combinations, HIPE.

This seemed like a good game to play with my sons. I explained the game, and then I gave them a simple example to be sure they understood.

ER

They quickly generated a long list of solutions, including:

- tERm
- obsERver
- fishERman
- buckminstERfullerene

Since that introduction a few weeks ago, the boys and I have played quite a few games. It’s a good activity to pass the time on a long car ride. The following are some of my favorites:

WKW

RTWH

RTHW

(these two are fun in tandem)HIPE

(the game’s namesake is a worthy adversary)TANTAN

The practice with my sons has made me a better-than-average HIPE player, so when I recently found myself needing to keep my sons busy while I prepared dinner, I offered the following challenge:

Create a HIPE for me that you think is difficult, and I’ll give you a nickel for every second it takes me to solve it.

Never one to shy away from a challenge, Eli attacked the problem with gusto. Fifteen minutes later, he announced, “Daddy, I have a HIPE for you,” and presented me with this:

RLF

That was three days ago. Sure, I could use More Words or some other website to find the answer, but that’s cheating. Winkler wrote, “Of course, you can find solutions for any of them easily on your computer… But I suggest trying out your brain first.”

The downside to relying on my brain? **This is gonna cost me a fortune.**

For your reading enjoyment, I’ve created the following HIPEs. They are roughly in order from easy to hard, and as a hint, I’ll tell you that there is a common theme among the words that I used to create them.

- MPL
- XPR
- YMM
- MSCR
- MPT
- ITESI
- NSV
- RIGON
- OEFF
- CTAH
- THME
- SJU
- TRAH (bonus points for finding more than one)

Winkler tells the story of how HIPE got him into Harvard. He wrote “The HIPE Story” as the essay on his admissions application, and four years later, he overheard a tutor who served on the admissions committee torturing a colleague with HIPEs and **calling them HIPEs**.

I can’t promise that HIPEs will get you into college, but hopefully you’ll have a little fun.