Langford's problem

Unsolved Hard Archive

archive posted 11 Jun 2026

Arrange the numbers $1, 1, 2, 2, \dots, n, n$ in a row so that for each $k$ exactly $k$ other numbers stand between the two copies of $k$ . For $n = 3$ the sequence 2, 3, 1, 2, 1, 3 works. For which $n$ is such an arrangement possible?

Posed by C. Dudley Langford, 1958

Like0

combinatorial-designs combinatorics

History and references

Solved in 1959 by Roy O. Davies.

C. Dudley Langford posed the problem in the Mathematical Gazette in 1958, and Roy O. Davies showed in 1959 that an arrangement exists exactly when $n \equiv 0$ or $3 (mod 4)$ . Necessity comes from adding up the positions of all $2 n$ numbers in two ways. If the first copy of $k$ sits at position $p_{k}$ , the second sits at $p_{k} + k + 1$ , and comparing with $1 + 2 + \dots + 2 n$ forces $\sum p_{k} = n (3 n - 1) /4$ , which is an integer only for $n \equiv 0, 3 (mod 4)$ . Sufficiency is shown by explicit constructions. Counting each sequence and its reversal once, there is 1 solution for $n = 3$ and for $n = 4$ , 26 for $n = 7$ and 150 for $n = 8$ , and the counts grow very quickly after that.

References

Solutions 0

Nobody has posted a solution here yet. Solutions written on Problempedia are credited to the people who write them.

References

Solutions 0

Discussion 0