Per la precisione, una qualunque sequenza di mosse che riporti la casella vuota nella posizione originaria comporta un riordinamento delle tessere che corrisponde in termini matematici ad una permutazione pari.
Le permutazioni pari di un certo numero (nel nostro caso 15) di oggetti sono esattamente la metà di tutte le permutazioni possibili, che sono 15! (15 fattoriale), per un totale di 15x14x13x12x11x10x9x8x7x6x5x4x3 configurazioni possibili.
Il dato importante per il signor Gedeone è che il semplice scambio di due tessere (quelle con i numeri 377 e 610 nel gioco con i numeri di Fibonacci) è una permutazione dispari, ovvero non è raggiungibile a partire dalla configurazione iniziale.
L'apparente contraddizione si risolve osservando che ci sono due tessere indistinguibili, quelle contrassegnate con il numero 1, e questa è l'unica vera differenza tra il gioco da noi proposto ed il gioco del 15 classico.
Evidentemente il signor Gedeone nel mescolare le tessere e nel riordinarle in seguito ha di fatto scambiato la posizione di queste due tessere indistinguibili, ottenendo in verità una posizione con due scambi: uno visibile tra le ultime due tessere, ed uno non evidente tra le prime due, e questa è una permutazione pari!
Per risolvere il gioco quindi il signor Gedeone dovrà scambiare tra loro le prime due tessere, e quindi risistemare nuovamente tutte le altre. Provateci e vedrete che magicamente anche le ultime due tessere andranno al loro posto!
Si può procedere ad esempio nel modo seguente:
Prima di tutto si trova una sequenza che effettui un doppio scambio tra tessere vicine, ad esempio la 89 con la 144 e la 377 con la 610. Una tale sequenza può essere ottenuta a partire dalla semplice successione di mosse N-O-S-E, che consiste nello spostare la casella vuota verso l'alto (Nord; ovvero spostare verso il basso la tessera che sta a nord della casella vuota), poi verso sinistra (Ovest), poi verso il basso (Sud) e infine verso destra (Est). Alla fine la casella vuota ritorna alla posizione originale, ma le tessere 89, 144, 610 vengono tra loro permutate in modo ciclico. Questa permutazione base può essere combinata con altre mosse semplici per ottenerne altre, ad esempio: O(NOSE)E, dove la parte tra parentesi è la nostra sequenza base, scambia tra loro le tessere 55, 89 e 377 (to be continued).
Successivamente si trova una sequenza che porti le tessere 610 e 377 al posto delle tessere 8 e 13, con la casella vuota nella posizione inizialmente occupata dalla tessera 5; non occorre che ci preoccupiamo di cosa succede alle altre tessere, ma dobbiamo stare attenti a non toccare le due tessere con il numero 1! La sequenza così trovata dovrà essere memorizzata, poiché dovremo riutilizzarla in seguito.
Ora possiamo scambiare tra loro le due tessere con 1 e simultaneamente le 377 con la 610, ora posizionate in modo da poter sfruttare le mosse trovate in precedenza.
Infine ripetiamo al contrario (senza fare errori!) la sequenza per riportare le tessere 377 e 610 nelle posizioni iniziali (ora scambiate di posto).
Questa sequenza di operazioni, dopo alcune ovvie semplificazioni, può essere ottimizzata, e ad esempio quella che segue è una soluzione in 50 mosse basata su questa argomentazione:
(NOOSENNOSSENNOSON)
(EENOSONEESOONESO)
(SENESSONNESSONEES)
La soluzione ottimale (quella che richiede il minor numero possibile di mosse) è stata trovata utilizzando un programma fatto appositamente da mio fratello Emanuele Paolini e da me leggermente adattato e consiste dalle seguenti 28 mosse:
NOONNESSSOONNESENNOOSSSENEES
C'è anche l'unica altra soluzione che si ottiene facendo tutte le mose al contrario
Il programm lo potete scaricare da qui