Il gioco del 15

Il gioco del 15 è famoso: si tratta di riordinare 15 caselle numerate da 1 a 15 disposte in una griglia 4×4. Anche l'immagine qua sopra è abbastanza famosa: è un enigma proposto da Sam Loyd relativo al gioco in questione. Riuscite a riordinare i numeri del gioco rappresentato in figura?

Se ancora non sapete la soluzione, non leggete oltre.

Se invece sapete già che la risposta è... (siamo sicuri che volete saperlo? bé, magari lo scrivo sotto, se sapete già la risposta è inutile che la ripeta proprio qua).

Comunque, se uno prova a cercare in giro la soluzione trova, su vari siti, che la risposta dipende da un problema di parità, ma la dimostrazione completa non la si trova quasi mai.

Ebbene, eccola qua. Una dimostrazione seria, come fanno i Veri Matematici.

Sia N il numero di coppie di numeri che non sono nel loro ordine naturale. Nell'esempio della figura N=1, perché la coppia (15,14) non è ordinata (mentre tutte le altre sono in ordine—occhio che bisogna considerare tutte le possibili coppie, cioè (1,2), (1,3), (1,4), ... , (2,3), (2,4), ... , (3,4), ... , (15,14). In sostanza, quando si parla di coppia si intende che si devono scegliere due numeri a caso, procedendo secondo il verso di lettura).

Invece di ragionare su spostamenti di caselle, conviene ragionare su spostamenti del buco.

Teorema dello spostamento orizzontale. Ogni spostamento del buco di uno spazio verso destra o verso sinistra lascia N costante.

Dimostrazione: uno spostamento a destra o a sinistra del buco non cambia l'ordine secondo cui sono disposte le caselle. CVD.

Teorema dello spostamento verticale. Ogni spostamento del buco di uno spazio verso l'alto o verso il basso fa aumentare o diminuire N di 3 unità.

Dimostrazione: uno spostamento del buco verso il basso cambia l'ordinamento della tessera spostata rispetto alle tre tessere precedenti. Viceversa, uno spostamento del buco verso l'alto cambia l'ordinamento rispetto alle tre tessere successive. CVD.

Teorema del ritorno. Qualunque movimento di tessere che riporti il buco nella posizione iniziale altera N di un numero pari di unità.

Dimostrazione: siccome il movimento orizzontale del buco è ininfluente, possiamo porre l'attenzione solo sui movimenti verticali. Perché il buco possa ritornare nella posizione di partenza, deve essere stato fatto un numero pari di movimenti verticali. Dunque N viene modificato secondo la formula



(dove a_n è uguale a 0 oppure a 1, a seconda di come viene cambiato l'ordinamento: abbiamo detto che N aumenta o diminuisce di 3, ma non sappiamo distinguere i due casi in generale, dipende dalle mosse che vengono fatte).

Anche se non sappiamo quanti sono gli a_n uguali a zero e quanti, invece, gli a_n uguali a uno, sappiamo però che questi sono sempre un numero pari. Possiamo pensare, allora, di accoppiare i valori di (-1)^a_n, cioè di sommarli due alla volta. Possono presentarsi solo quattro possibilità:
+1+1=2,
+1-1=0,
-1+1=0,
-1-1=-2,
e questi sono tutti numeri pari. CVD.

Allora possiamo dare una risposta al quesito iniziale: è possibile riordinare i numeri della figura? La disposizione iniziale ha N=1, quella richiesta ha N=0, e siccome N può variare soltanto di un numero pari di unità la disposizione iniziale non può essere riordinata come richiesto.