Frank Morgan

February 15, 2001

New US House Science Committee Chair Sherwood Boehlert (R-NY) listed science and math education as a top priority: “First, how can we attract more top students into science and math teaching? Second, how can we ensure that technology actually improves education? Third, how can we use exams in a way that promotes critical thinking, retention of knowledge and a love of learning?”

Old Challenge (Todd Feitelson). How many different strings of ten 1’s and 0’s are there such that no two 1’s are consecutive? That is,

1000101010 is acceptable, but 1000010110 is not acceptable.

Answer. 144. Strings of ten begin with either a 1 or a 0. If they begin with a 1, they must begin 10. Therefore, strings of ten can be written as:

0 + {valid strings of length nine} 10 + {valid strings of length eight}

So, the number of valid strings of length 10 equals the number of valid strings of length 9 plus the number of valid strings of length 8. In general, the number of valid strings of length n equals the number of valid strings of length n-1 plus the number of valid strings of length n-2.

There are two valid strings of length one (0, 1), and three valid strings of length two (10, 01, 00), and so the sequence becomes

2,3,5,8,13,21,34,55,89 and 144.

These are the famous “Fibonacci numbers.” Jeff Pierce points out an immediate application to seating teachers in a row of chairs with always at least one empty chair in between two teachers. Torsten Sillke observes that if one considers cyclic words (so 1********1 is forbidden too) one gets the “Lucas numbers.” Sillke posed a related question counting the independent sets of a graph.

Questionable Mathematics. Eric Brahinsky found in the San Antonio Express-News on February 7, 2001, in a column by Kathleen Parker on “Passing of time is not the enemy of man”:

Last weekend … I attended the 80th birthday party of my stepfather…. Beginning his eighth decade, Mauricio is a fully-employed practicing psychiatrist.

Of course a man turning 80 would be beginning his ninth decade, not his eighth.

Readers are invited to submit examples of questionable mathematics.

On Last Week’s Math Chat, John Hamilton, Torsten Sillke, and Mark Thompson report that the problem on “Well Arranged Sequences” is known as “Langford’s Problem,” attributed to C. Dudley Langford, a Scottish mathematician, who is supposed to have noticed the arrangement when his infant son was piling up a group of colored blocks; see http://www.lclark.edu/~miller/langford.html. It appears in Martin Gardner’s column in the December 1967 Scientific American and in his book Mathematical Magic Show. Hamilton adds, “Joseph DeVincentis’s proof seems similar to a proof I recall in Arthur Engel’s book Problem Solving Strategies where this problem (or one like it) is given. The number of solutions is the sequence A014552 at the On-Line Encyclopedia of Integer Sequences.”

Thompson continues:

As far as I know, I’m the first person to investigate “Langford Cycles”: I take two copies of the numbers 0 through N and arrange them on a circle, with 0 numbers between the two 0’s, etc. I included a “Langford Cycle” problem in a story that was published in GAMES magazine, November 1999, entitled “Numerology in the New Millennium.” In that story, I meet a young lady who turns out to be a clever numerologist, reminiscent of Martin Gardner’s Dr. Matrix character. She wears a necklace, “strung with glittering gold numerals like charms on a bracelet.” Toward the end of the story, “She laughed and took it off to show me. ‘There is no other like it; this is the only one. I had it custom-made, and the arrangement of the numbers is rather special. There are two each of the digits zero through eight. There are no digits between the two zeros, exactly one digit between the ones, two digits between the twos, three digits between the threes, and so on.’ She held it up against her other hand so I could see the numbers 7 1 6 0 0 2 in that order on the string. Can you deduce the positions of the other 12 digits?”
From a set of double-9 dominos (actually you only need the ones with numbers 0-8), you can construct a Langford cycle 18 numbers long, out of 9 dominos, including the 0-4, 0-8, 1-3, 2-5, and 5-8 dominos. There are 36 dominos with the numbers 0-8, not counting doublets, and it occurred to me that one might try to find _four_ Langford Cycles that could be made simultaneously without using the same domino twice. I don’t know whether that’s possible or not.

New Challenge. What kind of tax is best for the economy?

Send answers, comments, and new questions by email to [email protected], to be eligible for Flatland and other book awards. Winning answers will appear in the next Math Chat. Math Chat appears on the first and third Thursdays of each month. Prof. Morgan’s homepage is at www.williams.edu/Mathematics/fmorgan.

THE MATH CHAT BOOK, including a $1000 Math Chat Book QUEST, questions and answers, and a list of past challenge winners, is now available from the MAA (800-331-1622).

Copyright 2001, Frank Morgan.