Ian Stewart nel bel libro - La piccola bottega delle curiosità matematiche del professor Stewart – racconta che il matematico scozzese C. Dudley Langford stava osservando il figlio che giocava con 6 cubi colorati, 2 di ogni colore, notò che il ragazzo li aveva disposti in modo tale che i 2 cubi gialli erano separati da 1 cubo, i 2 cubi blu erano separati da 2 cubi e i 2 cubi rossi erano separati da 3 cubi. Ci pensò su e riuscì a dimostrare che si trattava dell’unica disposizione con questa proprietà (a parte quella simmetrica che si ottiene scambiando la destra con la sinistra).
E se i colori fossero 4 o più?
Per rispondere possiamo provare con carta e penna o
utilizzando 2 semi delle carte di un mazzo con i valori da 1 a 4. In modo più
completo, potremmo scrivere un programma con un linguaggio di programmazione
adatto per il calcolo numerico e provare tutte le combinazioni, selezionando
quelle che soddisfano le condizioni richieste.
Con 4 colori si ha
ancora un’unica combinazione:
Per quello che viene chiamato Problema di Langford, si hanno soluzioni per N = 3, 4, 7, 8, 11, 12, 15, 16, … (cioè uguali a 0 o 3, modulo 4); il corrispondente numero di soluzioni è 1, 1, 26, 150, 17792, 108144, 39809640, 326721800, … (sequenza OEIS A014552).
Si sono sempre tralasciate le soluzioni simmetriche.
Non ci sono invece soluzioni per gli altri valori (cioè
uguali a 1 o 2, modulo 4).
Il numero di soluzioni per N = 20 supera 2,6 x 1012
e per N = 24, 46 x 1015.
Questo argomento è già stato trattato in 2 precedenti Carnevali della Matematica nelle Notiziole di .mau. e prima in DropSea,
ma qui di seguito vorrei continuare mostrando alcuni esempi, oltre a quelli già
visti.
Tutti i 26 casi per N = 7 (che ha soluzioni perché 7 / 4 = 1 con resto 3)
Alcuni casi per N = 8
Un paio di casi per N = 12
12 5 3 7 11 4 3 5 6 10 4 7 9 12
8 6 11 1 2 1 10 2 9 8
12 5 9 7 4 2 11 5 2 4 10 7 9 12
8 6 3 1 11 1 3 10 6 8
Qui invece un esempio della sequenza di Skolem per N = 4, cioè dove la separazione non
è uguale al numero k, ma a k-1
2 3 2 4 3 1 1 4
Possiamo anche usare sequenze di Triplette di Langford, dove ogni numero
compare 3 volte, es. con N = 9
1 9 1 6 1 8 2 5 7 2 6 9
2 5 8 4 7 6 3 5 4 9 3 8 7 4 3
Se infine definiamo un insieme diverso di numeri che useremo come
sequenza base, al posto di {1,2,3,4}, allora possiamo potenzialmente
ottenere sequenze diverse, ad esempio, di seguito una sequenza di Skolem
usando l'insieme {2,3,5,6}
5 6 2 3 2 5 3 6
Problema
di Langford - Wikipedia
DropSea:
I rompicapi di Alice: I cubi di Langford
Il
problema di Langford | Notiziole di .mau.
oeis.org/A014552/a014552_1.txt
A014552 - Number of solutions to Langford
problem (up to reversal of the order):
0, 0, 1, 1, 0, 0, 26, 150, 0,
0, 17792, 108144, 0, 0, 39809640, 326721800, 0, 0, 256814891280, 2636337861200,
0, 0, 3799455942515488, 46845158056515936, 0, 0, 111683611098764903232,
1607383260609382393152, …
Non credo che sia nota una formula per il calcolo delle soluzioni, ma esiste comunque un modello che spiega abbastanza bene la variabilità dei dati
L’ordinata del grafico utilizza una scala logaritmica.
