Ciągiem Langforda nazywamy każdy taki ciąg długości \(2n,\) złożony z liczb \(1,1,2,2,\ldots,n,n,\) że dla każdego \(1\leqslant r\leqslant n\) pomiędzy wystąpieniami liczby \(r\) znajduje się dokładnie \(r\) liczb.
Nie ma ciągów Langforda dla \(n=1,2.\) Mając dane \(n=3,\) można wskazać tylko jeden (z dokładnością do rewersu) taki ciąg: \[2,\,3,\,1,\,2,\,1,\,3.\] Zachęcam do samodzielnego wyznaczenia ciągu Langforda dla \(n=4.\) Co ciekawe, nie ma ciągów Langforda dla \(n=5,6,\) ale dla \(n=7\) są – jednym z nich jest \[4,\ 6,\ 1,\ 7,\ 1,\ 4,\ 3,\ 5,\ 6,\ 2,\ 3,\ 7,\ 2,\ 5.\]
Ustalmy, dla jakich liczb naturalnych \(n\) może istnieć ciąg Langforda długości \(2n.\) Jeżeli w takim ciągu liczba \(r\) po raz pierwszy występuje na pozycji \(a_r,\) to jej drugie wystąpienie przypada na pozycję \((a_r+r+1).\) Zauważmy, że wśród liczb postaci \(a_r\) i (\(a_r+r+1\)) dla \(1\leqslant r\leqslant n\) każda z liczb \(1,2,\ldots,2n\) pojawia się dokładnie raz. Mamy zatem: \[\sum\limits_{r=1}^n(a_r+a_r+r+1)=\sum\limits_{i=1}^{2n}i.\] Powyższe równanie można łatwo przekształcić do postaci: \[\sum\limits_{r=1}^na_r=\frac{n(3n-1)}4,\] której lewa strona jest liczbą całkowitą – więc prawa też musi mieć tę własność. Wynika stąd, że \(n\) jest liczbą podzielną przez \(4\) lub przy dzieleniu przez \(4\) daje resztę \(3.\) Oznacza to, że dla tych liczb naturalnych \(n,\) których reszta z dzielenia przez \(4\) wynosi \(1\) lub \(2,\) nie ma ciągów Langforda długości \(2n.\)
Co ciekawe, prawdą jest również naturalne uzupełnienie powyższego stwierdzenia: jeżeli \(n\) przy dzieleniu przez \(4\) daje resztę \(0\) lub \(3,\) to istnieje ciąg Langforda długości \(2n\) (uzasadnienie tego faktu wymaga jednak trochę więcej finezji).
Czego zatem jeszcze o ciągach Langforda nie wiemy? Zdaje się, że wraz ze wzrostem odpowiednich wartości \(n\) liczba różnych ciągów Langforda długości \(2n\) rośnie bardzo szybko, ale nie ma dokładnego (nawet asymptotycznego) opisu tego wzrostu. Dla \(n=7\) istnieje \(26\) takich ciągów, dla \(n=8\) jest ich \(150,\) a największą dokładną wartością, jaką znamy, jest ta dla \(n=28,\) wynosząca nieco ponad półtora tryliarda.