La scorsa settimana avevo presentato il problema di Langford: mettere in fila $2n$ coppie di numeri da $1$ a $n$ in modo che tra i due numeri $i$ ci siano esattamente $i$ altri numeri. Per $n=3$ e $n=4$ le soluzioni (essenzialmente uniche) sono rispettivamente 3-1-2-1-3-2 e 4-1-3-1-2-4-3-2. Ho anche detto che una soluzione era possibile solo se il numero di coppie era della forma $4k$ oppure $4k+3$, come è stato dimostrato da Roy O. Davies. La dimostrazione è molto semplice: eccola qua.
Numeriamo da $1$ a $2n$ i numeri dell’elenco, e per ciascun numero $k \in {1, … n}$ consideriamo le due posizioni $P_k < Q_k$ dei due numeri nell'elenco. Nel caso $n=3$ abbiamo per esempio $P_1 = 2, Q_1 = 4, P_2 = 3, Q_2 = 6, P_3 = 1, Q_3 = 5.$ Chiaramente abbiamo $Q_k = P_k + k + 1$ per definizione di coppia $k$. La somma di tutti questi valori è $\sum_{k=1}^{n} (2P_k + k + 1) = 2\sum_{k=1}^{n} P_k + n + n(n+1)\!/\!2$, ma visto che sono i valori da $i$ a $2n$ sappiamo che la somma è anche $n(2n+1).$ Poiché la somma dei $P_k$ è evidentemente un numero intero, ci accorgiamo subito che se $n = 4q + 1$ oppure $n = 4q +2$ abbiamo che gli altri termini danno una somma frazionaria e quindi non ci sono soluzioni. □
Questo è un risultato negativo, nel senso che ci dice quando non si può risolvere il problema ma non quando lo si può fare. Però le soluzioni negli altri casi sono tantissime, a parte quella unica nei casi visti sopra. Davies pensava che per $n=7$ ci fossero 25 soluzioni, e Martin Gardner nel 1967 riportò quel valore: in realtà ce ne sono 26. John Miller, come scrive nel suo sito, programmò un computer nel 1968 e trovò le 26 soluzioni per $n=7$ e le 150 per $n=8$. (Due persone riuscirono a trovare tutte le soluzioni nel primo caso a mano…). E.J. Groth ottenne anche il numero di soluzioni per $n=11$ (17792) e $n=12$ (108144). Altri valori si possono trovare come sempre su OEIS: quelli per 15 e 16 sono stati computati negli anni ’80; il 19 nel 1999, il 20 nel 2002, il 23 nel 2004, il 24 nel 2005, il 27 e il 28 nel 2015… e poi non si sa più. Del resto, le soluzioni per $n=28$ sono 1607383260609382393152, diciamo parecchie!
Si può anche decidere di accettare solo le soluzioni “planari” al problema, nel senso che i numeri uguali si possono connettere tra loro e ottenere un grafo planare. La soluzione generale per $n=3$ è planare, quella per $n=4$ e quelle per $n=7$ non lo sono, ci sono quattro soluzioni planari per $n=8$ e così via. Come al solito, OEIS ha la successione. C’è poi la “variante Tanton”, da James Tanton: in questo caso ci sono $n$ studenti seduti in circolo, e si chiede che si può dare un numero da 1 a $n$ agli studenti in modo tale che se lo studente $k$ si sposta di $k$ posti in senso orario (quindi quello $n$ non si sposta…) alla fine non ci sia nessuno seduto sulle ginocchia di un altro. In questo caso si può dimostrare con semplici sistemi di parità che il numero di studenti deve essere dispari: stranamente la successione dei possibili valori (0, 0, 1, 0, 3, 0, 19, 0, 225, 0, 3441, 0, 79259, 0, 2424195…) non si trova su OEIS!
