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.