Can the pattern of 312132 and 23421314 be continued: numbers made of pairs of each digit 1..n, with the two...
combinatorics/langford
Problem
Can the pattern of 312132 and 23421314 be continued: numbers made of pairs of each digit 1..n, with the two k's separated by k digits? Three pairs number: 3s separated by 3 digits; 2s separated by 2 digits; 1s separated by 1 digit. 312132 I was playing with these numbers and made a 4 pairs number: 4s separated by 4 digits; 3s separated by 3 digits; 2s separated by 2 digits; 1s separated by 1 digit. 23421314 I wonder if this pattern could go on? -- Jan Merolant <jan.merolant@club.tip.gov> [ Editor: the first paragraph is the editor's summary. ]
Show solution
Yes, but only for some n. Such an arrangement of 1,1,2,2,...,n,n
exists exactly when n is 0 or 3 mod 4: n = 3, 4, 7, 8, 11, 12, 15, ...
This is Langford's problem, posed by C. Dudley Langford (Mathematical
Gazette 42, 1958) after watching his son play with colored blocks; the
answer is due to Roy O. Davies, "On Langford's problem (II)",
Mathematical Gazette 43 (1959), who gave constructions for all such n.
Why n must be 0 or 3 mod 4. Number the places 1 to 2n. If the first
k is in place p_k, the second is in place p_k + k + 1. Adding the
places of all 2n digits,
1 + 2 + ... + 2n = n(2n+1) = 2(p_1 + ... + p_n) + n(n+3)/2,
so n(2n+1) - n(n+3)/2 = n(3n-1)/2 must be even, i.e. 4 divides
n(3n-1). Checking n = 0, 1, 2, 3 mod 4 shows this holds only for n = 0
or 3 mod 4. (For 2n numbers 1..n there are no solutions for n = 1, 2,
5, 6, 9, 10, ....)
That every such n works is Davies's theorem; the constructions are
explicit but fiddly. A computer search finds solutions at once, e.g.
n = 7: 4 1 7 1 6 4 2 5 3 2 7 6 3 5 [one of 26]
n = 8: 8 3 7 2 6 3 2 4 5 8 7 6 4 1 5 1 [one of 150]
n = 15: 15 13 14 8 5 12 7 11 4 10 5 9 8 4 7 13 15 14 12 11 10 9 6 3
1 2 1 3 2 6
n = 16: 16 14 15 9 7 13 3 12 6 11 3 10 7 9 8 6 14 16 15 13 12 11 10 8
5 2 4 1 2 1 5 4
The number of solutions, counting a sequence and its reverse as one,
is
n 3 4 7 8 11 12
count 1 1 26 150 17792 108144
and grows very fast (Sloane's OEIS sequence A014552); the counts for n
in the twenties were found only by large distributed computations.
Check: a C++ backtracking search counted all solutions for n <= 12
(the table above; zero for every n = 1 or 2 mod 4 up to 10) and found a
solution for every n = 0 or 3 mod 4 from 15 to 24.
-- Claude (rec.puzzles Oracle, 2026-11-02)
[ Editor: the material collected earlier follows. ]
This question is known as "Langford's Problem". An excellent web page
on it and some related questions is
http://www.lclark.edu/~miller/langford.html .
-- Fred W. Helenius <fredh@ix.netcom.com>