Problema di Langford

Il problema di Langford (anche detto accoppiamento o sequenza di Langford) è un problema di combinatoria formalizzato dal matematico scozzese C. Dudley Langford.^[1] Consiste nell'individuare una sequenza finita di ${\displaystyle 2n}$ numeri interi da ${\displaystyle 1}$ a ${\displaystyle n}$, dove ciascun numero compare esattamente due volte e la distanza tra le due occorrenze equivale al numero stesso.

Esempio di una soluzione al problema di Langford

Storia

La prima formalizzazione del problema venne pubblicata da Langford nel 1958 dopo aver osservato suo figlio giocare con dei cubi colorati.^[1] Langford notò che la curiosa disposizione di sei cubi di tre colori diversi messi in fila era l'unica possibile per quel numero di cubetti (eccetto la soluzione speculare) che rispettasse la regola di inclusione: ad ogni colore associò un numero e quel numero corrispondeva al numero di altri blocchi inclusi tra due dello stesso colore. Aggiunse un'altra coppia di cubetti colorati ed ottenne una nuova soluzione unica del problema per quel numero di blocchi.

Nella figura sono presenti le soluzioni del problema per ${\displaystyle n=3}$ e ${\displaystyle n=4}$.

Langford ha generalizzato il problema individuando alcune soluzioni per ${\displaystyle n}$ = 3, 4, 7, 8, 11, 12 e 15, e dichiarando l'assenza di altre soluzioni per ${\displaystyle n\leq 15}$.

Definizione

Una sequenza che risolve il problema di Langford contiene numeri interi ${\displaystyle k=1,2,...,n}$ presenti a coppie. Ogni numero ${\displaystyle k}$ compare due volte nella sequenza, una in posizione ${\displaystyle a_{k}}$ e una in posizione ${\displaystyle b_{k}}$, tali che ${\displaystyle b_{k}-a_{k}=k+1}$.^[2]

Varianti

La stessa variante del problema è stata proposta in momenti diversi da Thoralf Skolem^[3] e R. S. Nickerson.^[4] 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.^[5]

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. 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.^[6] Una sequenza corretta 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.

Generalizzazione

È possibile definire una generalizzazione che raccolga sia il problema originale che la variante di Skolem-Nickerson in un'unica formulazione. Il problema quindi diventa trovare ${\displaystyle n}$ e un insieme di interi ${\displaystyle T=\{t_{1},t_{2},...,t_{n}\}}$ per cui è possibile comporre una sequenza con coppie di interi dall'insieme ${\displaystyle S=\{s_{1},s_{2},...,s_{n}\}}$ tale che

${\displaystyle \qquad b_{k}-a_{k}=t_{k}+1,\quad k=1,2,...,n}$

dove ${\displaystyle a_{k}}$ e ${\displaystyle b_{k}}$ sono la prima e la seconda posizione di ${\displaystyle s_{k}}$ nella sequenza. Per le sequenze di Langford ${\displaystyle T=\{2,3,...,n+1\}}$ e ${\displaystyle S=\{1,2,...,2n\}}$, mentre per le sequenze di Skolem-Nickerson ${\displaystyle T=\{1,2,...,n\}}$ e ${\displaystyle S=\{1,2,...,2n\}}$. Definendo l'insieme ${\displaystyle S=\{d,d+1,...,n-1,n\}}$, ${\displaystyle d}$ è detto scarto e assume valore 1 sia per il problema di Langford che per la variante di Skolem-Nickerson.

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 un carattere (tipicamente indicato con 0, * o _) che non possiede nessun gemello. Una sequenza di Langford agganciata con ${\displaystyle n=2}$ è 1, 2, 1, *, 2, mentre l'analoga sequenza di Skolem-Nickerson è 1, 1, 2, *, 2.^[2]

Notazione

• L(2,n) denota il numero di soluzioni del problema di Langford con ${\displaystyle n}$ coppie di numeri
• V(2,n) denota il numero di soluzioni della variante del problema
• L(s,n) e V(s,n) sono una generalizzazione delle notazioni precedenti per istanze di ordine superiore ${\displaystyle s}$

Soluzioni

Roy O. Davies ha dimostrato che le soluzioni al problema di Langford L(2, n) esistono per ${\displaystyle n=4m-1}$ e ${\displaystyle n=4m}$.^[7] Di seguito sono elencate quante soluzioni del problema sono tutt'ora note per le principali formulazioni.^[8]

${\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	?	-	-
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.^[9]