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⁵ possible codes, so entering all of them sequentially would require 5 × 10⁵ 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.

1. Construct a de Bruijn sequence that contains every two-digit permutation of 0’s and 1’s.
2. Construct a de Bruijn sequence that contains every three-character permutation from an alphabet with three characters.
3. 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.

Mathiest Fortnight of 2016

Monday, April 4, 2016, was Square Root Day, because the date is abbreviated 4/4/16, and 4 × 4 = 16. But if you’re a faithful reader of this blog, then you already knew that, because you read all about it in Monday’s post, Guess the Graph on Square Root Day.

But it doesn’t end there. It ain’t just one day. Oh, no, friends… this is a banner week. Or, really, a banner two weeks.

Tomorrow, April 8, 2016, is a geometric sequence day, because the date is 4/8/16, and 4 × 2 = 8, and 8 × 2 = 16.

And Saturday, April 9, 2016, is a consecutive square number day, because the month, day, and year are consecutive square numbers. Square number days, in which each of the month, day, and year are all square numbers — not necessarily consecutive — are less rare; there are 15 of them this year. But among them is 1/4/16, which rocks the intersection of square number days and geometric sequence days. (That’s right — I said “rocks the intersection.”)

And then Sunday, April 10, 2016, is an arithmetic sequence day, because 4, 10, and 16 have a common difference of 6. Though honestly, arithmetic sequence days are a dime a half-dozen; there are six of them this year.

Next Monday, April 12, 2016, is a sum day, because 4 + 12 = 16. Again, ho-hum. There are a dozen sum days this year, and there will be a dozen sum days every year through 2031.

And just a little further in the future is Friday, April 16, 2016, whose abbreviation is 4/16/16, and if you remove those unsightly slashes, you get 41,616 = 204². I’m not sure what you’d call such a day, other than awesome.

Admittedly, some of those things are fairly common occurrences. But, still. That’s six calendar-related phenomena in a thirteen-day period, which may be enough mathematic-temporal mayhem to unseat the previously unrivaled Mathiest Week of 2013.

Partially, this blog post was meant to enlighten and entertain you. But mostly, it was meant to send numerologists off the deep end. Mission. Accomplished.

You’ve endured enough. Here are some calendar-related jokes for you…

Did you hear about the two grad students who stole a calendar?
They each got six months!

I was going to look for my missing calendar, but I just couldn’t find the time.

What do calendars eat?
Dates.

Making Progress, Arithmetically

Today is 11/12/13, a rather pleasant-sounding date because the numbers form an arithmetic sequence, albeit a trivial one. It’s not the only date in 2013 for which the month, date, and year form an arithmetic sequence. How many others are there?

Several nights ago, my sons asked if they could do bedtime math, but Eli asked if we could do problems other than those on the Bedtime Math website, because “they’re a little too easy.” So instead, I navigated to the MathCounts website and opened the 2013-14 MathCounts School Handbook. We scrolled to page 9 and attacked the problems in Warm-Up 1.

Things were going well until we reached Problem 8 in the set, which read:

The angles of a triangle form an arithmetic progression, and the smallest angle is 42°. What is the degree measure of the largest angle of the triangle?

Eli asked, “Daddy, what’s an arithmetic progression?” pronouncing arithmetic as “uh-rith-ma-tick” instead of “air-ith-met-ick.”

I could have just answered Eli’s question by stating the definition:

An arithmetic progression is a sequence of numbers for which there is a common difference between terms.

But such a definition isn’t very helpful, since I’m not sure that either Eli or Alex know what sequence, common difference, or term mean. It would have led to even more questions.

Plus, I’ve always believed that kids understand (and retain) more when they discover things on their own. Call it “discovery learning” or “inquiry-based instruction” or any of myriad other names from educational jargon, it just means that giving kids the answer is not the most effective way for them to learn.

So instead, I said, “Let me give you some examples.” And then I wrote:

1, 2, 3

3, 5, 7

Alex said, “Oh, I get it! An arithmetic progression is a nice pattern of numbers.”

So I said, “Well, let me give you some patterns that aren’t arithmetic progressions.” And then I wrote:

2, 4, 8

“That’s a nice pattern, isn’t it?” I asked. “But it’s not an arithmetic progression.”

“Oh,” said Alex. He thought for a second, then revised. “You have to add the same amount every time.”

And there you have it. Three examples, and my sons were able to define arithmetic progression. It’s not as sophisticated as “a common difference between terms,” but “add the same amount every time” is a sufficient definition for a six-year-old.

So they generated an arithmetic progression with 42 as the smallest term:

42, 45, 48

Eli said, “I don’t fink vat’s enough.” When asked to explain, he said he thought that the angles in a triangle add up to 180 degrees.

“Are you sure?” I asked. He wasn’t. Nor was Alex. So I asked if they could convince themselves that the sum of the angles is 180°.

Alex said, “Well, the angles in a square add up to 360°, and you could cut it in half.” So we did:

They then reasoned that each triangle would have a sum of 180°. “But maybe that only works for a square,” I said. “How do you know it’ll work for other shapes?”

Eli suggested that we could cut a rectangle in half, too:

And again they concluded that each triangle would have a sum of 180°.

Understand, this is NOT a proof of the triangle sum formula. When they get to high school and need to demonstrate the rigor that the Common Core State Standards are demanding, well, then we’ll worry about formal proof. But for now, I’m okay with six-year-olds who can demonstrate that kind of reasoning.

They then took another guess, but this time they chose three numbers that added to 180:

42, 59, 79

Realizing that the difference between the first and second terms was 17 and the difference between the second and third terms was 20, they revised:

42, 60, 78

They concluded that the largest angle had a measure of 78°. And all was right with the world.

So why am I telling you all this?

Partially, it’s because I’m a proud father.

But more importantly, it’s because this vignette demonstrates that teaching is an art, and successful teaching doesn’t happen by accident. It’s not easy, as many people believe. What’s easy is the perpetuation of bad teaching, a la Charlie Brown’s teacher, or textbooks that simply present information with the belief that students will absorb it by osmosis. Good teaching, however, requires content knowledge and pedagogical knowledge, and it demands teachers who can handle unexpected classroom twists and turns and have the ability to adjust on the fly.

A student is convinced that a right triangle isn’t a right triangle because the right angle isn’t in the lower left corner? You better find an effective way to clarify that misconception. (Hint: Don’t use a traditional textbook where every picture of a right triangle shows the right angle in the lower left corner.)

Students think that 16/64 = 1/4 because you can “cancel the 6’s”? Uh-oh. Better find some counterexamples pronto, and help them understand why 16/64 can be reduced to 1/4.

Your students don’t know the definition of arithmetic progression? Then you better figure out a way to help them define it, and just writing your definition on the chalkboard isn’t gonna cut it.

Want to see what good teaching looks like? See Dan Meyer, or Christopher Danielson, or Fawn Nguyen. Or many, many others who don’t blog about it but inspire students every day.

Someday soon, I hope to add my project at Discovery Education to the list of examples of good teaching. Until then, I’ll just keep blathering about my sons.

Mathiest Week of 2013

Can you hear it? That’s the sound of the awesomeness approaching.

It starts this Wednesday.

5/8/13

The month, date and year are consecutive terms in the Fibonacci sequence.

It continues on Thursday.

5/9/13

The numbers form an arithmetic sequence.

And then there’s Sunday.

5/12/13

That’s a Pythagorean triple.

Arithmetic sequence dates are a dime a dozen. In fact, there are six of them in 2013 alone. Pythagorean dates and Fibonacci dates are far more rare. There are only eight Pythagorean dates and six Fibonacci dates in the entire 21st century. To have all of them occur within a six-day span is incredible.

How will you celebrate?

Celebrity Sighting at Math Meeting

I have the pleasure of serving on the advisory committee for the Math Midway 2 Go, a traveling exhibit of the Museum of Mathematics. I get to see a lot of cool stuff.

When it opens on December 15, MoMath will be the only museum of mathematics in North America. If you happen to find yourself in Manhattan, check it out. The exhibits are really fun.

One of the exhibits in the Math Midway 2 Go is a number line with ornaments hanging from each number. For instance, a square ornament hangs from the numbers 1, 4, 9, 16, …, and a symbol that looks like an atom hangs from 2, 3, 5, 7, 11, 13, … (the atom symbol was used because “prime numbers are the building blocks of the number system”). However, I was not able to identify the symbol that hangs from the following numbers:

3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30,
32, 34, 40, 48, 51, 60, 64, 68, 80, 85, 96

I’ve been told that the symbol is a compass (the kind for drawing circles, not for orienteering). Unfortunately, that hint didn’t help me to identify the sequence of numbers. Do you know what the sequence is? **

A recent meeting of the advisory committee was held at a private school in NYC, and a number of parents were waiting in the hallway when our meeting ended. As I walked by, one of the parents stood up quickly, and I accidentally brushed against her. “Oh, I’m sorry, ma’am,” I said. She turned to look at me, and I looked back. First, I noticed how tall she was. Then I noticed something else. “Oh,” I said, “you’re Brooke Shields.” Turns out her kids go to this school. She smiled politely at my recognition.

She was dressed in casual clothes, and she was just there to pick up her kids. I didn’t want to be a nuisance, so I just said, “Have a great day.”

How cool is that? Go to a math meeting, meet a celebrity! And one I had a crush on when I was 13, no less!

** The sequence is the number of sides for constructible polygons, which are regular polygons that can be drawn with a straightedge and compass.

On To The Next…

Another year almost over, the next one about to begin. Which makes me think of sequences…

Math jokes make all my Cauchy sequences converge.

And here’s a Fox Trot cartoon with sequences:

You undoubtedly can identify the first sequence: 1, 1, 2, 3, 5, 8, 13, …
Of course, it’s the Fibonacci sequence.

But do you recognize the sequence from the last panel? It begins 3, 0, 2, 3, 2, 5, …

If not, here’s your first question:

What’s the next term in that sequence?

And your second question:

What is the general formula for the terms in that sequence? (A recursive formula is completely acceptable. The explicit formula is quite a beast.)

Like the Fibonacci sequence, this sequence is defined by a recurrence relation. In particular,

P(0) = 3, P(1) = 0, P(2) = 2, and P(n) = P(n – 2) + P(n – 3)

This sequence has an amazing property: For any natural number n, if n is prime, then n | P(n). No, really. You can check for yourself. P(3), P(5), and P(7) are trivial, since P(3) = 3, P(5) = 5, and P(7) = 7. But…

P(11) = 22, and 11|22

P(13) = 39, and 13|39

P(17) = 119, and 17|119

P(19) = 209, and 19|209

P(23) = 644, and 23|644

Also like the Fibonacci sequence, the ratio of consecutive numbers in this sequence have a constant ratio. As we all know, the ratio of consecutive Fibonacci numbers is approximately 1.618034, better known as the golden ratio. For the Perrin sequence, the ratio of consecutive numbers is approximately 1.324718, known as the plastic constant.

Cool stuff.

Here are a couple other sequences for you to ponder as you prepare for the new year. Can you determine the next term?

O, T, T, F, F, S, S, E, …

3, 3, 5, 4, 4, 3, 5, 5, …

6, 14, 24, 36, 50, …