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

Storia La prima formalizzazione del problema venne pubblicata da Langford nel 1958 dopo aver osservato suo figlio giocare con dei cubi colorati. 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 e .

Langford ha generalizzato il problema individuando alcune soluzioni per = 3, 4, 7, 8, 11, 12 e 15, e dichiarando l'assenza di altre soluzioni per .

Definizione Una sequenza che risolve il problema di Langford contiene numeri interi presenti a coppie. Ogni numero compare due volte nella sequenza, una in posizione e una in posizione , tali che .

Variante di Skolem-Nickerson La stessa variante del problema è stata proposta in momenti diversi da Thoralf Skolem e R. S. Nickerson. 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 .

In questo caso una sequenza valida per è 4, 2, 3, 2, 4, 3, 1, 1; inoltre si noti che i numeri 1 devono sempre apparire in diretta successione..

Secondo la formalizzazione di Skolem, poi estesa da Václav Linek anche alle sequenze di Langford, definiti gli insiemi di interi in successione e una sequenza che risolve il problema è una partizione di in coppie tali che per .

Una sequenza è detta di Skolem di ordine se e ; per la sequenza scritta sopra ad esempio il partizionamento di equivale a . Una sequenza è detta di Langford di ordine e scarto se e ; 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, e in diversi altri problemi combinatori.

Generalizzazioni Insiemi di ordine superiore 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. 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 è 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.

Sequenze agganciate ed estese 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.

Una sequenza che possiede esattamente una soluzione vuota è detta "estesa". Una sequenza di Langford estesa con è 1, 2, 1, *, 2, mentre l'analoga sequenza di Skolem-Nickerson è 1, 1, 2, *, 2. È sempre possibile individuare una sequenza di Skolem-Nickerson estesa per qualunque , e il numero di soluzioni è almeno .

Soluzioni Soluzioni planari Un sottoinsieme delle soluzioni del problema di Langford sono le cosiddette soluzioni planari, proposte da Donald Knuth in The Art of Computer Programming, 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 .

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".

Numero di soluzioni

Roy O. Davies ha dimostrato che le soluzioni al problema di Langford L(2, n) esistono solo per multipli di 4 e i loro diretti predecessori. Analogamente per V(2,n) esistono soluzioni solo per multipli di 4 e i loro diretti successori, e sono almeno . Per L(3, n) possono esistere soluzioni solo per gli multipli di 9 e i loro diretti successori e predecessori.

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

CoppieL(2,n) CoppieV(2,n) TripletteL(3,n) TripletteV(3,n) QuadrupleL(4,n) 1 - 1 - 1 - 2 - - - - - 3 1 - - - - 4 1 3 - - - 5 - 5 - - - 6 - - - - - 7 26 - - - - 8 150 252 -. - - 9 - 3 9 - 10 - - 5 20 - 11 - - 33 - 12 - - - 13 - - - - 14 - - - - - 15 - - - - 16 - - - 17 - - - 18 - - - 19 - - 20 - - 21 - - - - 22 - - - - - 23 - - - - 24 ? - - 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.

Note

Bibliografia

Collegamenti esterni

Categoria:Successioni di interi Categoria:Combinatoria