Il gioco del 15

Versione didattica in javascript

La domanda è: il gioco, a volte riesce e a volte non riesce; perché?

E ancora: se il gioco è inizialmente impostato con i numeri in ordine inverso da 15 a 1, non si riesce a disporli in ordine diretto; perché?

 

Il gioco è risolubile solo per alcune configurazioni iniziali.
Per stabilire se è risolubile è utile definire i concetti di inversione e di parità.

• Se la tessera contenente il numero i compare "prima" di n numeri minori di i allora chiamiamo questa situazione una inversione di ordine n e la chiamiamo n_i.

NOTA. I numeri vanno letti da destra a sinistra e dall'alto in basso come se fossero in una unica striscia.

Quindi definiamo:

dove la sommatoria deve partire da 2 perché non ci sono numeri minori di 1.

Più semplicemente si può dire che N = i(p) è il numero di inversioni della permutazione di numeri che al momento compare nel gioco.

N può essere pari o dispari.

Nel seguente esempio N = 1 è dispari. 2 infatti compare prima di un solo numero minore di 2.

• Se N è pari il gioco è risolvibile.
• Se N è dispari il gioco non è risolvibile.

Vogliamo dimostrarlo?

Più tardi...

Esercizio.
Qual è la parità del numero di inversioni N del seguente quadrato?

Le inversioni per ogni numero sono rispettivamente: 12, 9, 9, 5, 4, 4, 3, 3, 0, 3, 3, 2, 1, 1, and 0.
La loro somma N = 59, dispari.
Dunque il gioco non può essere risolto.

Altra domanda: qual è la parità del gioco in cui i numeri sono disposti nell'ordine inverso da 15 a 1?

Il massimo numero di mosse necessarie per risolvere il goco generalizzato del 15 con n*n caselle, con n = 1, 2, 3, ... è: 0, 6, 31, 80, ... (Sloane's A087725).