Langford and Skolem Sequences

The Scottish mathematician C. Dudley Langford proposed a problem in 1958 after watching his little boy play with colored cubes. The child placed three pairs of blocks in a line so that between the two red blocks there was one block, between the two blue blocks there were two blocks, and between the two yellow blocks there were three blocks. He also managed to add two green blocks with four blocks in-between and keep the above properties after some rearrangements.

Replacing cubes with numbers 1, 2, ..., n the question which is now known as Langford's problem asks for what n is it possible to arrange pairs of integers 1, 2, ..., n so that the first occurrence of 1 ≤ k ≤ n happens in position ak and the second at bk such that

(1) bk - ak = k + 1,   k = 1, 2, ..., n.

An example of a sequence (Langford's sequence, of course, or Langford's string), for n = 4 is not difficult to find: 41312432. In other words, there are 4 positions between the two 4s, 3 between the two 3s, 2 between the 2s, and 1 between the 1s.

In a parallel development the Swedish mathematician Th. Skolem discussed in 1957 a similar problem with (1) replaced by

(2) bk - ak = k,   k = 1, 2, ..., n.

The latter has been rediscovered by R. S. Nickerson in 1966 and a solution supplied by D. C. B. Marsh in 1967. For n = 4 we have an example: 42324311.

Both problems have been generalized under a unique umbrella: for what n and a set of integers T = {t1, t1, t2, ..., tn} it is possible to arrange pairs of numbers from the set S = {s1, s2, ..., sn} such that

(3) bk - ak = tk,   k = 1, 2, ..., n,

where ak, bk are the first and second locations of sk in the arrangement. For Langford's sequences, T = {2, 3, ..., n+1}, S = {1, 2, ..., 2n}. For the Skolem sequences, T = {1, 2, ..., n}, S = {1, 2, ..., 2n}.

Wherever S = {d, d+1, ..., n-1, n}, d is called a defect, so that both Langford's and the Skolem sequences have defect 1.

Further generalization allows for one or more empty (non-numeric) terms usually denoted by "*" or "_". Sequences without empty terms are called perfect, those with a single empty term in the position next to last are called hooked. 121*2 is an example of a hooked Langford sequence with defect 1. 112*2 is a similar example of a Skolem sequence.

Finally, a problem has also been posed where one considers triplets or even quadruplets of numbers instead of pairs [Gardner, pp. 23-26].

The applet bellow allows for experimentation with Langford and Skolem sequences. The parameters are as follows:

  • N is the largest number in the sequence,
  • D is the smallest number in the sequence, so that set S = {D, D+1, ..., N},
  • M, which may be 2 or 3, indicates whether numbers from S come in pairs or triplets,
  • H is the number of "empty" terms.

For any combination of N, D, M, H, the applet displays the necessary strings at the bottom and the corresponding number of rectangles - sequence positions - for the strings to be dragged into.

If you are reading this, your browser is not set to run Java applets. Try Firefox and declare the site http://www.cut-the-knot.org as trusted in the Java setup.

Langford and Skolem Sequences

What if applet does not run?

Discussion

References

  1. M. Gardner, The Colossal Book of Short Puzzles and Problems, W.W. Norton & Company, 2006
  2. C. D. Langford, Problem, Math Gaz, 42 (1958) 228.
  3. V. Linek, Extending Skolem sequences, how can you begin?, Australasian Journal of Combinatorics 27(2003), pp.129-137
  4. R. S. Nickerson, D. C. B. Marsh, Problem E1845, Am Math Monthly, Vol. 74, No. 5. (May, 1967), pp. 591-592.
  5. Th. Skolem, On Certain Distributions of Integers in Pairs with Given Differences, Math. Scand. 5 (1957) 57-58.

|Activities| |Contact| |Front page| |Contents| |Store| |Algebra|

Copyright © 1996-2017 Alexander Bogomolny

Langford and Skolem Sequences

For the original Langford's and Skolem's sequences, i.e., for the perfect sequences with defect equal to 1 as defined in (1) and (2), we have the following

Theorem 1

Langford sequences exist iff for n = 0 or -1 (mod 4). Skolem sequences exist iff for n = 0 or 1 (mod 4).

Proof of necessity

Let there be a Langford sequence for some n. The positions are then labeled by set 1, 2, ..., 2n. Let 1 occupy positions a1 and b1 = a1 + 2, and, more generally, k = 1, 2, ..., n occupy positions ak and bk = ak + k+1. Then adding up all the indices in two ways we get

Σak + Σbk = 1 + 2 + ... + 2n,

with the sums from k = 1 through k = n. In other words,

2Σak + n(n + 1)/2 + n = n(2n + 1),

which simplifies to

Σak = (3n2 - n)/4.

Note that the sum on the left being a sum of indices is an integer; thus the right hand side is also an integer which means that 3n2 - n is bound to be divisible by 4. By direct verification, this only happens when n = 0 or -1 (mod 4).

For a Skolem sequence, we would similarly have

Σak = (3n2 + n)/4,

which is integer only if n = 0 or 1 (mod 4).

... to be continued ...

|Activities| |Contact| |Front page| |Contents| |Store| |Algebra|

Copyright © 1996-2017 Alexander Bogomolny

 61256500

Search by google: