rec.puzzles Archive

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>