martedì 4 dicembre 2007

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 an è 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 an uguali a zero e quanti, invece, gli an uguali a uno, sappiamo però che questi sono sempre un numero pari. Possiamo pensare, allora, di accoppiare i valori di (-1)an, 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.

23 commenti:

Anonimo ha detto...

Io avevo un giochino come quello... tu avevi le tessere con tutti i numeri fino al 15, le mischiavi e poi le dovevi riordinare ^^
era carino :)

Ronkas ha detto...

Sì, io sapevo la soluzione.
Mi ci scervellai sopra per ore per poi scoprire che qualche furbone (o meglio, furbona) l'aveva "aggiustato" con una configurazione impossibile, staccando i pezzettini di plastica...


:/

Anonimo ha detto...

e in premio c'era un milione di dollari, giusto? :D

zar ha detto...

Non so se c'era anche un premio in denaro, a dir la verità.

Anonimo ha detto...

Salve ho visto che trattate il problema del 15, di cui ero un grande appassionato da bambino. Ora, mi piacerebbe fare una tesina per la SSIS su questo gioco. Conoscete qualche articolo di matematica che parla di questo gioco?
Grazie,
matteo

zar ha detto...

No, ma c'è questo meraviglioso articolo che ne parla con dovizia di particolari... :-)

Unknown ha detto...

ma sono l'unico che ha capito come si fa in 2 3 partite????
la soluzione è semplice e non uso nessun stratagemma matematico (forse lo è ma nn l'ho letto da nessuna parte:) e non ci metto più di 2 minuti a risolverlo XD

zar ha detto...

Igor, quello della figura non lo risolvi :-)

Unknown ha detto...

sicuramente sarà matematicamente impossibile XD magari se la trovassi questa combinazione ci insisterei un pò XD

Unknown ha detto...
Questo commento è stato eliminato dall'autore.
zar ha detto...

Prova pure, ma non ci si può riuscire...

Anonimo ha detto...

Anche se ho letto diversi siti non ho capito il discorso delle coppie del numero N!
In pratica leggendo dal numero in alto a sinistra verso destra e via verso il basso in base a quanti numeri non sono consecutivi il valore di N aumenta ai 1 ?
Quindi se i primi due numeri sono 1,15 N=1 e se dopo il 15 c'è 2 N sempre uguale 1 ?

zar ha detto...

No, non "consecutivi" ma "in ordine".

Se hai 1,15,2 hai le seguenti coppie:

1,15 - ordinata
1, 2 - ordinata
15,2 - non ordinata: N=1

Anonimo ha detto...

Scusate, ma io non riesco a trovare un algoritmo decente per controllare se la mia combinazione casuale di tesserine è risolvibile o meno..
In pratica se n è pari è risolvibile,
mentre se n è dispari non lo è..giusto?
quindi io devo controllare ogni possibile coppia da destra verso sinistra, dall'alto verso il basso..
quindi o dovrei controllare tutte queste coppie?
(1,2)(1,3)(1,4)(1,5)(1,6)etc..
(2,3)(2,4)(2,5)(2,6)etc..
e se trovassi una coppia(6,3) n=1
e se ne trovassi un'altra (12,11) n=2...e alla fine dovrebbe essere risolvibile dato che n è pari..
puo essere cosi oppure ho sbagliato de tutto?
Grazie

zar ha detto...

Esatto, è così.

Andrea ha detto...

Grazie! e l'ipotetico numero 16 non va considerato, giusto?

zar ha detto...

No, il 16 non esiste, non si deve considerare.

Andrea ha detto...

Quindi questo calcolo vale sempre, indipendentemente dalla posizione in cui si trova lo spazio vuoto?

zar ha detto...

Oh, uhm, no, direi di no. Ci devo pensare un po', ma i teoremi che ho scritto riguardano lo spostamento del buco dalla posizione "giusta". Se non è già lì, probabilmente non funziona.

Andrea ha detto...

Era proprio questo, dopo ore e ore di studio del mio programma ce l'ho fatta!! Se lo spazio vuoto(il mio sedici) non è all'ultima posizione in basso a destra, N risulta errato! Grazie mille dell'aiuto!

zar ha detto...

Direi questo: il 16 può spostarsi in orizzontale senza problemi (N non cambia), ma se si sposta in verticale N cambia di 3, e questo non va bene.

Andrea ha detto...

Si, giusto!
Grazie mille per l'aiuto, è stato determinante!

Unknown ha detto...

Noi, generazione anni 70/80 senza pc o grandi calcoli matematici, già all'età di 8/10 anni lo terminavamo in 2 o 3 minuti...poi ci sfidavamo tra amici solo sulla velocità perchè tutti erano in grado di risolverlo.