## Frank Morgan's Math Chat |

February 15, 2001

**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
Frank.Morgan@williams.edu, 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.