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 a_k and the second at b_k such that

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

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 = {t₁, t₁, t₂, ..., t_n} it is possible to arrange pairs of numbers from the set S = {s₁, s₂, ..., s_n} such that

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.

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.

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₁ and b₁ = a₁ + 2, and, more generally, k = 1, 2, ..., n occupy positions a_k and b_k = a_k + k+1. Then adding up all the indices in two ways we get

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

which simplifies to

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 3n² - 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

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

... to be continued ...