Problema di Langford

La stessa variante del problema è stata proposta in momenti diversi da Thoralf Skolem^[4] e R. S. Nickerson.^[5] Quest'ultima prevede che le distanze tra ogni coppia di numeri siano inferiori a 1 rispetto alla formulazione originale. Date le variabili di prima, la variante può essere espressa come ${\displaystyle b_{k}-a_{k}=k}$.

In questo caso una sequenza valida per ${\displaystyle n=4}$ è 4, 2, 3, 2, 4, 3, 1, 1; inoltre si noti che i numeri 1 devono sempre apparire in diretta successione.^[6]

Secondo la formalizzazione di Skolem,^[4] poi estesa da Václav Linek anche alle sequenze di Langford,^[7] definiti gli insiemi di interi in successione ${\displaystyle D=\{d_{1},d_{2},...,d_{n}\}}$ e ${\displaystyle S=\{s_{1},s_{2},...,s_{2n}\}}$ una sequenza che risolve il problema è una partizione di ${\displaystyle S}$ in coppie ${\displaystyle \{(a_{i},b_{i})\}_{i=i}^{n}}$ tali che ${\displaystyle b_{i}-a_{i}=d_{i}}$ per ${\displaystyle 1\leq i\leq n}$.

Una sequenza è detta di Skolem di ordine ${\displaystyle n}$ se ${\displaystyle D=\{1,...,n\}}$ e ${\displaystyle S=\{1,...,2n\}}$; per la sequenza scritta sopra ad esempio il partizionamento di ${\displaystyle S}$ equivale a ${\displaystyle \{(7,8),(2,4),(3,6),(1,5)\}}$. Una sequenza è detta di Langford di ordine ${\displaystyle n}$ e scarto ${\displaystyle d}$ se ${\displaystyle D=\{d,...,d+n-1\}}$ e ${\displaystyle S=\{1,...,2n\}}$; nella definizione generale lo scarto assume valore 2.

Le sequenze di Skolem trovano applicazione nella teoria dei disegni, in particolare è possibile ricavare un sistema di terne di Steiner a partire da una sequenza di Skolem,^[8][9] e in diversi altri problemi combinatori.^[10]

Il problema di Langford può essere risolto non solo considerando coppie di numeri, ma anche triplette o in generale insiemi di ordine superiore a 2, come proposto da Frank S. Gillespie e Winfiled R. Utz.^[11] In questi casi la distanza dev'essere garantita tra un numero e il suo successivo omologo nella sequenza, per tutte le volte in cui questo compare. Esiste la sotto-variante di Skolem-Nickerson anche per questa generalizzazione.

Una sequenza corretta di Langford con triplette di numeri e ${\displaystyle n=9}$ è 3, 4, 7, 9, 3, 6, 4, 8, 3, 5, 7, 4, 6, 9, 2, 5, 8, 2, 7, 6, 2, 5, 1, 9, 1, 8, 1.

Un'ulteriore generalizzazione denota come "perfette" le sequenze esposte finora, dove tutti i numeri presenti sono coinvolti in un collegamento, e introduce delle sequenze "agganciate" (hooked in inglese) che ammettono la presenza di caratteri neutri (tipicamente indicati con 0, * o _) che non possiedono nessun gemello e stanno a indicare delle posizioni vuote nella sequenza. Un esempio di sequenza agganciata di Skolem-Nickerson è 2, 4, 2, *, 3, 4, *, 3, 1, 1.^[7]

Una sequenza che possiede esattamente una soluzione vuota è detta "estesa". Una sequenza di Langford estesa con ${\displaystyle n=2}$ è 1, 2, 1, *, 2, mentre l'analoga sequenza di Skolem-Nickerson è 1, 1, 2, *, 2.^[3] È sempre possibile individuare una sequenza di Skolem-Nickerson estesa per qualunque ${\displaystyle n\geq 1}$, e il numero di soluzioni è almeno ${\displaystyle 2^{\lfloor n/3\rfloor }}$.^[12]

Un sottoinsieme delle soluzioni del problema di Langford sono le cosiddette soluzioni planari, proposte da Donald Knuth in The Art of Computer Programming,^[13] e sono tali se, tracciando degli archi che connettono ciascuna coppia di numeri, questi non si intersecano mai. Nella figura seguente c'è un esempio di soluzione planare per ${\displaystyle n=8}$.

Un'altra versione meno stringente consente che gli archi possano girare intorno alla sequenza partendo dall'alto e arrivando al basso e viceversa. Esse sono dette soluzioni planari "con scappatoia".^[14]

Roy O. Davies ha dimostrato che le soluzioni al problema di Langford L(2, n) esistono solo per ${\displaystyle n}$ multipli di 4 e i loro diretti predecessori.^[15] Analogamente per V(2,n) esistono soluzioni solo per ${\displaystyle n}$ multipli di 4 e i loro diretti successori, e sono almeno ${\displaystyle 2^{\lfloor n/3\rfloor }}$.^[16] Per L(3, n) possono esistere soluzioni solo per gli ${\displaystyle n}$ multipli di 9 e i loro diretti successori e predecessori.^[17]

Di seguito sono elencate quante soluzioni del problema sono tutt'ora note per le principali formulazioni.^[18]

${\displaystyle n}$	Coppie L(2,n)	Coppie V(2,n)	Triplette L(3,n)	Triplette V(3,n)	Quadruple L(4,n)
1	-	1	-	1	-
2	-	-	-	-	-
3	1	-	-	-	-
4	1	3	-	-	-
5	-	5	-	-	-
6	-	-	-	-	-
7	26	-	-	-	-
8	150	252	-[19]	-	-
9	-	1 328	3	9	-
10	-	-	5	20	-
11	17 792	-	-	33	-
12	108 144	227 968	-	-	-
13	-	1 520 280	-	-	-
14	-	-	-	-	-
15	39 809 640	-	-	-	-
16	326 721 800	700 078 384	-	-	-
17	-	6 124 491 248	13 440	-	-
18	-	-	54 947	200 343	-
19	256 814 891 280	-	249 280	869 006	-
20	2 636 337 861 200	5 717 789 399 488	-	4 247 790	-
21	-	61 782 464 083 584	-	-	-
22	-	-	-	-	-
23	3 799 455 942 515 488	-	-	-	-
24	46 845 158 056 515 940	?	-	-	3
25	-	?	-	-	?
26	-	-	?	-	?
27	?	-	?	?	?
28	?	?	?	?	?
29	-	?	-	?	?

Il numero di soluzioni del problema originale, ovvero i valori di L(2,n) al variare di n, fanno a loro volta parte di una sequenza nell'On-Line Encyclopedia of Integer Sequences.^[20]