Mathematical Games

This page gives the exact text of Martin Gardner's columns relating to Langford's Problem. Note that he revisits the problem in Mathematical Magic Show, published by Alfred A. Knopf, ISBN 0-88385-449-X, first and second editions.

November 1967, pages 127-128

6. Many years ago C. Dudley Langford, a Scottish Mathematician, was watching his little boy play with colored blocks. There were two blocks of each color, and the child had piled six of them in a column in such a way that one block was between the red pair, two blocks were between the blue pair and three were between the yellow pair. Substitute digits 1, 2, 3 for the colors and the sequence can be represented as 312132.

This is the unique answer (not counting its reversal as being different) to the problem of arranging the six digits so that there is one digit between the 1's and there are two digits between the two 2's and three digits between the two 3's.

Langford tried the same task with four pairs of differently colored blocks and found that it too had a unique solution. Can the reader discover it? A convenient way to work on this easy problem is with eight playing cards: two aces, two deuces, two threes and two fours. The object is to place them in a row so that one card separates the aces, two cards separate the deuces, and so on.

There are no solutions to "Langford's problem", as it is now called, with five or six pairs of cards. There are 25 distinct solutions with seven pairs. No one knows how to determine the number of distinct solutions for a given number of pairs except by exhaustive trial-and-error methods, but perhaps the reader can discover a simple method of determining if there is a solution. Next month I shall make some remarks about the general case and cite major references.

December 1967, pages 131-132

The unique solution to Langford's Problem with four pairs of cards is 41312432. It can be reversed, of course, but this is not considered a different solution.

If n is the number of pairs, the problem has a solution only if n is a multiple of four or one less than such a multiple.

Gardner cites references for Langford, Priday, Davies, Gillespie and Utz, and Nickerson as given in the bibliography.

March 1968, page 124

In giving C. Dudley Langford's problem of arranging n pairs of objects in a row such that one object separates one pair, two objects separate another pair, and so on to n objects between the nth pair, I said that there were 25 distinct solutions, not counting reversals as being different. This figure, taken from a journal reference cited in December, is short by one. James Bartow and Gerald K. Schoenfeld, each working by hand, found 26 solutions. This was confirmed by five separate computer programs written by Malcolm C. Holtje, John Miller, Robert A. Smith, Glenn F. Stahly and Thomas Starbird. The first four programs also found 150 solutions for n=8. There are no solutions unless n is a multiple of four or one less. E. J. Groth, an engineer with Motorola, Inc., at the Aerospace Center in Scottsdale, Arizona, used a program coded in FORTRAN to extend the count to 17,792 sequences for n = 11 and to 108,144 for n = 12. The printout for the two sets of solutions is a stack of about 3,000 sheets.
Used by Permission.