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) | b_{k} - a_{k} = 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) | b_{k} - a_{k} = 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
(3) | b_{k} - a_{k} = t_{k}, k = 1, 2, ..., n, |
where a_{k}, b_{k} are the first and second locations of s_{k} 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.
What if applet does not run? |
References
- M. Gardner, The Colossal Book of Short Puzzles and Problems, W.W. Norton & Company, 2006
- C. D. Langford, Problem, Math Gaz, 42 (1958) 228.
- V. Linek, Extending Skolem sequences, how can you begin?, Australasian Journal of Combinatorics 27(2003), pp.129-137
- R. S. Nickerson, D. C. B. Marsh, Problem E1845, Am Math Monthly, Vol. 74, No. 5. (May, 1967), pp. 591-592.
- Th. Skolem, On Certain Distributions of Integers in Pairs with Given Differences, Math. Scand. 5 (1957) 57-58.
|Activities| |Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander BogomolnyLangford 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 a_{1} and
Σa_{k} + Σb_{k} = 1 + 2 + ... + 2n,
with the sums from k = 1 through k = n. In other words,
2Σa_{k} + n(n + 1)/2 + n = n(2n + 1),
which simplifies to
Σa_{k} = (3n^{2} - 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
For a Skolem sequence, we would similarly have
Σa_{k} = (3n^{2} + n)/4,
which is integer only if n = 0 or 1 (mod 4).
... to be continued ...
|Activities| |Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny