Il Gioco dei 15 è un classico rompicapo che è fu antenato dei fenomeni virali nell’America dell’Ottocento e a volte può essere impossibile da risolvere.

Qualcuno di voi, rovistando in cantina o in soffitta, potrà ritrovare un esemplare del “Gioco dei 15″. Questo rompicapo consiste nel muovere quindici tessere numerate in una griglia quadrata di sedici caselle. La casella che resta vuota permette di spostare una tessera alla volta. Normalmente, all’inizio le tessere sono in ordine sparso e lo scopo del gioco è quello di posizionarle in modo ordinato con i numeri da 1 a 15 ( qui una versione online del gioco).

Nessuno si aspetterebbe mai che un innocuo passatempo da spiaggia sia stato il protagonista di una “febbre” che invase l’America e poi si allargò anche nel resto del mondo durante il Diciannovesimo secolo. Infatti, a partire dal 1879, quando il gioco fece la sua comparsa a New York, crebbe vertiginosamente di popolarità e si diffuse rapidamente in tutti gli Stati Uniti per poi arrivare in Europa e perfino in Australia e Nuova Zelanda durante i primi mesi del 1880.

Ciò che però trasformò il gioco in una psicosi collettiva fu il fatto che spesso, partendo da una certa configurazione iniziale, il miglior risultato che si riusciva a raggiungere era la configurazione in cui tutte le tessere erano in ordine tranne quelle del 14 e del 15, che erano invertite. Qualsiasi tentativo di andare avanti, ottenendo  la configurazione con l’ordine giusto era un fallimento. Presto il risolvere il gioco avendo all’inizio solo il 14 e 15 scambiati ne divenne una particolare versione, chiamata 14-15 Puzzle, e si trasformò in una vera sfida.

I giornali dell’epoca riportano vari episodi che descrivono l’impatto virale che ebbe il gioco sulla popolazione nel corso di pochi mesi. Ricompense molto generose (fino a 1000$) o anche più fantasiose (un dentista mise in palio un set di denti finti) venivano offerte a chi avesse trovato la soluzione. In maniera piuttosto enfatizzata si racconta di come i manicomi si fossero riempiti di persone ossessionate dal diabolico rompicapo, paragonandolo a una pestilenza.

Una classica versione del gioco dei 15 risolto. Fonte immagine: Shutterstock

 

Ovviamente, non passò molto tempo prima che qualcuno dimostrasse che il 14-15 Puzzle era matematicamente impossibile da risolvere. Per capirlo, basta applicare un po’ di algebra delle permutazioni. Avendo un insieme qualsiasi, ne facciamo una permutazione se semplicemente cambiamo l’ordine dei suoi elementi. Le permutazioni che incontriamo più spesso sono gli anagrammi. Per esempio, se prendiamo la strana parola SCIENTIFICAST, consideriamo l’insieme delle lettere {S,C,I,E,N,T,I,F,I,C,A,S,T} e ne facciamo una permutazione otteniamo la combinazione altrettanto strana FINSISCETTICA.

Prendiamo ora come insieme quello formato dai numeri da 1 a 15: {1,2,…,15}. Una permutazione si può scrivere ad esempio come (2 6 9 11 13), vuol dire che il 2 va al posto del 6, il 6 va al posto del 9 e avanti fino a che il 13 va al posto del 2. In questo modo avremo la configurazione {1,13,3,4,5,2,7,8,6,10,9,12,11,14,15}. Di solito, ogni permutazione si scompone in trasposizioni, ossia permutazioni che scambiano solo due elementi. Quindi, la permutazione precedente si può scomporre come (2 6 9 11 13) = (2 6)(6 9)(9 11)(11 13).

Le permutazioni si dividono in pari o dispari a seconda che si possano scomporre rispettivamente in un numero pari o dispari di trasposizioni. La proprietà fondamentale per quello che vogliamo dimostrare è che, combinando due permutazioni pari, si ottiene di nuovo una permutazione pari, invece combinando una permutazione dispari con una pari, se ne ottiene una dispari.

Torniamo allora al gioco dei 15. Ogni volta che si esegue una mossa, i numeri nella griglia cambiano di posto, e questo si può intendere come l’aver compiuto una particolare permutazione sull’insieme {1, … ,15}. La configurazione giusta con le tessere in ordine da 1 a 15 è vista come permutazione “zero” e considerata pari. Quello che si dimostra è che la permutazione associata a ogni mossa è sicuramente pari. Di conseguenza, solo se la configurazione iniziale è il risultato di una permutazione pari, allora attraverso un certo numero di mosse (tutte permutazioni pari) sarà possibile ottenere la configurazione esatta.

Chiaramente, la configurazione del 14-15 Puzzle  con il 14 e il 15 scambiati è data dalla sola trasposizione (14 15), che è indubbiamente dispari e per questo motivo non può essere risolto. E anche nella versione classica del gioco, quando partendo da una configurazione qualsiasi, si arriva ad avere 14 e 15 invertiti, significa che la configurazione iniziale era una permutazione dispari e nessuna sequenza di mosse permetterebbe di raggiungere mai la soluzione.

In generale, tutte le possibili configurazioni iniziali sono date dalle possibili permutazioni su un insieme di 15 elementi, che sono 15!, cioè 15 fattoriale (= 1*2*3*4..*15), di cui metà sono pari e metà dispari. Se il gioco comincia con una delle 15!/2 configurazioni buone, cioè quelle pari, è sempre possibile risolverlo senza bisogno di impazzire, basta armarsi della dovuta pazienza!

Per saperne di più:

Archer, Aaron F. (1999), “A modern treatment of the 15 puzzle”, The American Mathematical Monthly, 106 (9): 793–799,

Pekonen, Osmo & Shcum, Jerry & Sonneveld, Die & Archer, Aaron. (2007). The 15 puzzle: how it drove the world crazy. The Mathematical Intelligencer. 29. 10.1007/BF02986216.

Johnson, Wm. Woolsey; Story, William E. (1879), “Notes on the “15” Puzzle”, American Journal of Mathematics, 2 (4): 397–404,

Immagine di copertina: numero astratto – casuale vintage tipografia in legno stampa blocchi in una scatola di legno isolato su bianco, marekuliasz via Sutterstock