Frank Morgan

February 1, 2001

Old Challenge (Walter Wright). Consider the sequence: 3 1 2 1 3 2. It consists of a pair of 1’s separated by one other number, a pair of 2’s separated by two other numbers, and a pair of 3’s separated by three other numbers. Can you find a similar sequence with a pair of 4’s too? More?

Answer. Yes with 4’s: 4 1 3 1 2 4 3 2. Not with 5’s or 6’s. Al Zimmermann did a computer search up through 12’s:

He guessed that there are solutions if and only if N is a multiple of 4 or one less than a multiple of 4. Joseph DeVincentis came up with a clever proof (reproduced below) that other numbers cannot work. Walter Wright, the proposer, wrote: “I read many years ago (in one of Martin Gardner’s Scientific American columns, I think), that [there is a solution] if and only if N is a multiple of 4 or one less than a multiple of 4. I also read that no general formula had been found to describe how to arrange the sequences–in other words, the only known way was (and probably still is) by brute strength.” He was unable to locate the reference. He did provide a solution with 24’s:

24 22 23 19 17 21 13 20 10 8 18 4 1 16 1 15 4 14 8 10 13 12 17 19 22 24 23
21 20 18 16 15 14 11 12 7 9 3 5 2 6 3 2 7 5 11 9 6.

Here is Joseph DeVincentis’s proof that N has to be a multiple of 4 or one less than a multiple of 4:

Since the ones are 2 places apart, the twos 3 places apart, and so on, until the N’s are N+1 places apart, the sum of the differences of the places where each number occurs is 2 + 3 + . . . + (N+1). This has the same parity (odd or even) as the sum of all the places, 1 + 2 + . . . + 2N. If N is even, this means that N/2 (the number of odd terms in the first sum) has the same parity as N (the number of odd terms in the second sum), and N must be a multiple of 4. If N is odd, it means that (N-1)/2 has the same parity as N, and N must be one less than a multiple of 4.

New 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.

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.