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.
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.
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.
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.
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 from MG.
6. LANGFORD'S PROBLEM
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 e's and three digits between the 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 then 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 26 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.
6. 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 4 or one less than such a multiple. C. Dudley Langford posed his problem in The Mathematical Gazette (Vol. 42, October 1958, page 228). For subsequent discussion see C. J. Priday, "On Langford's Problem (I)", and Roy 0. Davies, "On Langford's Problem (II)", both in The Mathematical Gazette (Vol.43, December 1959, pages 250-55).
The 26 solutions for n = 7 are given in The Mathematical Gazette (Vol. 55, February 1971, page 73). Numerous computer programs have confirmed this list, and found 150 solutions for n = 8. E. J. Groth and John Miller independently ran programs which agreed on 17,792 sequences for n = 11, and 108,144 for n = 12.
R. S. Nickerson, in "A Variant of Langford's Problem", American Mathematical Monthly (Vol. 74, May 1967, pages 591-95), altered the rules so that the second card of a pair, each with value k, is the kth card after the first card; put another way, each pair of value k is separated by k-1 cards. Nickerson proved that the problem was solvable if and only if the number of pairs is equal to 0 or 1 (modulo 4). John Miller ran a program which found three solutions for n=4 (they are 11423243, 11342324, and 41134232); five solutions for n=5; 252 solutions for n=8; and 1,328 for n=9.
Frank S. Gillespie and W. R. Utz, in "A Generalized Langford Problem", Fibonacci Quarterly (Vol. 4, April 1966, pages 184-86), extended the problem to triplets, quartets, and higher sets of cards. They were unable to find solutions for any sets higher than pairs. Eugene Levine, writing in the same journal ("On the Generalized Langford Problem", Vol. 6, November 1968, pages 135-38), showed that a necessary condition for a solution in the case of triplets is that n (the number of triplets) be equal to -1, 0, or 1 (modulo 9). Because he found solutions for n = 9, 10, 17, 18, and 19, he conjectured that the condition is also sufficient when n exceeds 8. The nonexistence of a solution for n=8 was later confirmed by a computer search.
Levine found only one solution for n=9. I know of no other solution; perhaps it is unique. Readers may enjoy finding it. Take from a deck all the cards of three suits which have digit values (ace through nine). Can you arrange these 27 cards in a row so that for each triplet of value k cards there are k cards between the first and second card, and k cards between the second and third? It is an extremely difficult combinatorial puzzle.
D. P. Roselle and T. C. Thomasson, Jr., "On Generalized Langford Sequences", Journal of Combinatorial Theory (Vol. 11, September 1971, pages 196-99), report on some new non-existence theorems, and give one solution each for triplets when n = 9, 10, and 17. So far as I am aware, no Langford sequence has yet been found for sets of integers higher than three, nor has anyone proved that such sequences do or do not exist.
JM Note -- See Table of Solutions page for the most recent info on these variations and higher order arrangements. [LINK]