## Skolem Sequence Example Essay

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

(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 T = {t_{1}, t_{1}, t_{2}, ..., t_{n}} it is possible to arrange pairs of numbers from the set S = {s_{1}, s_{2}, ..., s_{n}} such that

(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.

Discussion

### 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 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 a_{1} and b_{1} = a_{1} + 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

Σ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 3n^{2} - 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

Σ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Кроме того, тот старик вроде бы обо всем позаботился. - Канадец. - Да. Он вызвал «скорую». Мы решили уйти.

## One thought on “Skolem Sequence Example Essay”