Il gioco del 15

[3m0o]

Conoscete tutti il famoso rompicapo del 15? Su di una tavoletta 4x4 vi sono quindici tessere numerate dal 1 fino al 15 inoltre vi è uno spazio vuoto che ci permette di cambiare di posizione alle tessere adiacenti.
L'obbiettivo è ottenere una configurazione particolare a partire da una data. Ad esempio la Schylling vende questo rompicapo e te lo da nella configurazione iniziale seguente, dove con X intendo lo spazio vuoto.
|-------------------|
| 01 | 03 | 05 | 07 |
|-------------------|
| 09 | 11 | 13 | 15 |
|-------------------|
| 02 | 04 | 06 | 08 |
|-------------------|
| X | 10 | 12 | 14 |
|-------------------|

E spostando le caselle bisogna arrivare ad una configurazione richiesta. Ovviamente possiamo solo spostare le tessere adiacenti a quella vuota vuota. Ad esempio dalla figura data possiamo fare come prima mossa solamente una delle seguenti due
Mossa 1.a)

|-------------------|
| 01 | 03 | 05 | 07 |
|-------------------|
| 09 | 11 | 13 | 15 |
|-------------------|
| X | 04 | 06 | 08 |
|-------------------|
| 02 | 10 | 12 | 14 |
|-------------------|

oppure
Mossa 1.b)

|-------------------|
| 01 | 03 | 05 | 07 |
|-------------------|
| 09 | 11 | 13 | 15 |
|-------------------|
| 02 | 04 | 06 | 08 |
|-------------------|
| 10 | X | 12 | 14 |
|-------------------|

Sul retro della scatola del giochino prodotto dalla Schylling ti propongono le seguenti 6 configurazioni da ottenere
Configurazione 1: dall'1 al 15.

|-------------------|
| 01 | 02 | 03 | 04 |
|-------------------|
| 05 | 06 | 07 | 08 |
|-------------------|
| 09 | 10 | 11 | 12 |
|-------------------|
| 13 | 14 | 15 | X |
|-------------------|

Configurazione 2: dal 15 all'1

|-------------------|
| 15 | 14 | 13 | 12 |
|-------------------|
| 11 | 10 | 09 | 08 |
|-------------------|
| 07 | 06 | 05 | 04 |
|-------------------|
| 03 | 02 | 01 | X |
|-------------------|

Configurazione 3: in verticale

|-------------------|
| 01 | 05 | 09 | 13 |
|-------------------|
| 02 | 06 | 10 | 14 |
|-------------------|
| 03 | 07 | 11 | 15 |
|-------------------|
| 04 | 08 | 12 | X |
|-------------------|

Configurazione 4: Dispari/Pari 1

|-------------------|
| 01 | 03 | 02 | 04 |
|-------------------|
| 05 | 07 | 06 | 08 |
|-------------------|
| 09 | 11 | 10 | 12 |
|-------------------|
| 13 | 15 | 14 | X |
|-------------------|

Configurazione 5: Dispari/Pari 2

|-------------------|
| 01 | 09 | 02 | 10 |
|-------------------|
| 03 | 11 | 04 | 12 |
|-------------------|
| 05 | 13 | 06 | 14 |
|-------------------|
| 07 | 15 | 08 | X |
|-------------------|

Configurazione 6: Dispari/Pari 3

|-------------------|
| 01 | 04 | 05 | 08 |
|-------------------|
| 02 | 03 | 06 | 07 |
|-------------------|
| 09 | 10 | 13 | 14 |
|-------------------|
| X | 11 | 12 | 15 |
|-------------------|

Ecco l'immagine del retro della scatola del gioco prodotto dalla Schylling



Trovare l' "errore" commesso dagli ingegneri della Schylling!

[axpgn]

Non sono granché nel contare gli "scambi" ... comunque mi pare che la configurazione data sia dispari mentre le altre sono tutte pari tranne una quindi è impossibile arrivarci (tranne una )

Cordialmente, Alex

[Super Squirrel]

Io ne conto rispettivamente $0$, $105$, $36$, $4$, $28$ e $12$.

[3m0o]

"axpgn":

Non sono granché nel contare gli "scambi" ... comunque mi pare che la configurazione data sia dispari mentre le altre sono tutte pari tranne una quindi è impossibile arrivarci (tranne una )

Cordialmente, Alex

"Super Squirrel":

Io ne conto rispettivamente $ 0 $, $ 105 $, $ 36 $, $ 4 $, $ 28 $ e $ 12 $.

Per entrambi (edit)

Non so cosa intendete veramente con parità della configurazione. Piuttosto sarebbe meglio dire la parità della permutazione che prende la configurazione iniziale e restituisce quella finale. Ad ogni modo, credo abbiate sbagliato entrambi a contare o a trarre qualche deduzione dalla parità
Perché le parità di una permutazione che porta dalla configurazione iniziale a quella finale sono
1) censurato (nell'edit )
2) censurato
3) censurato
4) censurato
5) censurato
6) censurato

Non ho capito quindi quali sono le configurazioni che voi dite che non è possibile ottenere?
Edit:
Ho capito cosa intendete per parita della configurazione. Intendete la parità della permutazione che vi porta da
\[ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,X \]
alla configurazione.

Okay penso allora abbiate contato bene. Ma continuo a non capire quali configurazioni non sono possibili ottenere

ps: ho censurato perché probabilmente deducevate la risposta da quello che ho scritto, e pensavo intendesse qualcosa d'altro con parità della configurazione

[axpgn]

Non volevo intervenire perché è un "classico" ben conosciuto (o almeno mi pare visto che la mania inizio centocinquant'anni fa ) poi però ho visto che l'obiettivo era più vario e ho postato, restando però volutamente sul vago

"3m0o":
Ho capito cosa intendete per parita della configurazione. Intendete la parità della permutazione che vi porta da
\[ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,X \]
alla configurazione.

A dir la verità, io ho fatto riferimento non a quella "standard" qui citata da te (non so come venga denominata ) ma a quella di partenza del giochino.

"3m0o":Okay penso allora abbiate contato bene. Ma continuo a non capire quali configurazioni non sono possibili ottenere

Tutte tranne una (non me lo ricordo più quale e non ho voglia di ricontare )

Cordialmente, Alex

[3m0o]

"axpgn":Non volevo intervenire perché è un "classico" ben conosciuto (o almeno mi pare visto che la mania inizio centocinquant'anni fa ) poi però ho visto che l'obiettivo era più vario e ho postato, restando però volutamente sul vago

Tutte tranne una (non me lo ricordo più quale e non ho voglia di ricontare )

Cordialmente, Alex

Allora no, hai sbagliato!

edit:

E non intendo a contare la parità.

[axpgn]

Tutte buone tranne una: quella "invertita"; dove avrei sbagliato?

Cordialmente, Alex

[3m0o]

"axpgn":

Tutte buone tranne una: quella "invertita"; dove avrei sbagliato?

[quote="3m0o"]Okay penso allora abbiate contato bene. Ma continuo a non capire quali configurazioni non sono possibili ottenere

Tutte tranne una (non me lo ricordo più quale e non ho voglia di ricontare )
Cordialmente, Alex

[axpgn]

Hai capito male!

Perché bisbigli? Tanto si legge lo stesso

In realtà, avevo contato bene le configurazioni di arrivo ma avevo sbagliato proprio quella di partenza (mi era venuta dispari ... $7 xx 6$ invece di $7 xx 8$ )

Cordialmente, Alex

[3m0o]

Non ci sto capendo più nulla ahahah
perché bisbiglio?? In che senso?

ma 7x6 è pari...

[3m0o]

Ad ogni modo avete capito qual'è il problema: io ho fatto così

È noto che ogni permutazione è data dal prodotto di trasposizioni. Inoltre è noto che la parità di tali trasposizioni rimane invariata. Ovvero se la permutazione \( \sigma \) è scomponibile in un prodotto pari di trasposizioni allora ogni scomposizione in prodotto di trasposizioni conterrà un numero pari di trasposizioni (in modo analogo con un numero dispari di trasposizioni).

Quindi possiamo uscire dalle regole del gioco per dimostrare che la configurazione 2 non è possibile ottenerla.
Scriviamo semplicemente in fila in ostri 15 numeri e la \(X\) in questo modo
\[ 1,3,5,7,9,11,13,15,2,4,6,8,X,10,12,14 \]

Notiamo che siccome le mosse legali sono fare sempre una trasposizione con \(X\) e che la \(X\) dalla configurazione iniziale alla configurazione finale differisce di tre posizioni verso destra deduciamo che il numero di mosse in alto equivale al numero di mosse verso il basso (perché arriviamo sempre nella quarta fila). Mentre il numero di mosse verso destra eccede di 3 rispetto al numero di mosse verso sinistra (perché la \(X\) nella configurazione finale si trova a destra di 3 posizioni rispetto alla configurazione iniziale).

Pertanto dalla configurazione iniziale alla configurazione 1 utilizzeremo un numero dispari di trasposizioni.

Troviamo una permutazione dalla configurazione iniziale a quella 1. Essa è
\[
2 \leftrightarrow 3 \\
3 \leftrightarrow 5 \\
4 \leftrightarrow 7 \\
5 \leftrightarrow 9 \\
6 \leftrightarrow 11 \\
7 \leftrightarrow 13 \\
8 \leftrightarrow 15 \\
10 \leftrightarrow 13 \\
12 \leftrightarrow 15 \\
13 \leftrightarrow X \\
14 \leftrightarrow X \\

\]
e sono 11, quindi la parità è soddisfatta.

Per la configurazione 2, è più facile partire dalla configurazione 1. Notiamo che siccome la \(X\) non cambia di posto dalla configurazione 1 alla 2 allora il numero di mosse verso l'alto è uguale al numero di mosse verso il basso, così come il numero di mosse verso destra è uguale al numero di mosse verso sinistra. Pertanto se esiste un prodotto di trasposizioni dalla 1 alla 2 essa avrà un numero pari di trasposizioni.
A partire da
\[ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,X \]
dobbiamo arrivare a
\[ 15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,X \]
Notiamo che la seguente permutazione è dispari
\[
1 \leftrightarrow 15 \\
2 \leftrightarrow 14 \\
3 \leftrightarrow 13 \\
4 \leftrightarrow 12 \\
5 \leftrightarrow 11 \\
6 \leftrightarrow 10 \\
7 \leftrightarrow 9 \\
\]
che è un numero dispari di trasposizioni, quindi dalla 1 non possiamo arrivare alla 2. Deduciamo pertanto che dalla configurazione iniziale non possiamo arrivare alla configurazione 2.

Per la configurazione 3 partiamo sempre dalla 1 e dobbiamo arrivare a
\[ 1,5,9,13,2,6,10,14,3,7,11,15,4,8,12,X\]
ecco una permutazione pari
\[
15 \leftrightarrow 12 \\
7 \leftrightarrow 10 \\
8 \leftrightarrow 14 \\
4 \leftrightarrow 13 \\
3 \leftrightarrow 9 \\
2 \leftrightarrow 5 \\

\]
è pertanto possibile ottenerla dalla configurazione iniziale.

Per la configurazione 4 pariamo sempre dalla configurazione 1 e voilà una permutazione pari che ci porta a
\[ 1,3,2,4,5,7,6,8,9,11,10,12,13,15,14,X \]
\[
3 \leftrightarrow 2 \\
7 \leftrightarrow 6 \\
11 \leftrightarrow 10 \\
15 \leftrightarrow 14 \\
\]
La parità è soddisfatta

Per la configurazione 5 pariamo sempre dalla configurazione 1 e voilà una permutazione pari che ci porta a
\[ 1,9,2,10,3,11,4,12,5,13,6,14,7,15,8,X \]
\[
9 \leftrightarrow 5 \\
10 \leftrightarrow 6 \\
11 \leftrightarrow 7 \\
12 \leftrightarrow 8 \\
9 \leftrightarrow 3 \\
10 \leftrightarrow 4 \\
13 \leftrightarrow 7 \\
14 \leftrightarrow 8 \\
9 \leftrightarrow 2 \\
11 \leftrightarrow 4 \\
13 \leftrightarrow 6 \\
15 \leftrightarrow 8 \\
\]
La parità è soddisfatta!

Mentre per la configurazione 6, partiamo da quella iniziale, e dev'essere pari anche qui la permutazione poiché la \(X\) inizia e termina nella stessa posizione. Dunque ecco una permutazione
\[
2 \leftrightarrow 9 \\
4 \leftrightarrow 11 \\
6 \leftrightarrow 13 \\
8 \leftrightarrow 15 \\
3 \leftrightarrow 4 \\
7 \leftrightarrow 8 \\
11 \leftrightarrow 10 \\
15 \leftrightarrow 14 \\
\]
Che è pari.

Ricapitolando siccome una permutazione che prende quella iniziale e restituisce quella richiesta è di parità
1) Dispari
2) Dispari
3) Dispari
4) Dispari
5) Dispari
6) Pari

ma siccome con le regole del gioco possiamo fare delle permutazione tra quella iniziale a quella finale di parità
1) Dispari
2) Pari
3) Dispari
4) Dispari
5) Dispari
6) Pari

La seconda configurazione non può essere fatta

[axpgn]

@3m0o

Scrivere con un carattere piccolo equivale a bisbigliare ...

Ovviamente hai ragione, scherzavo (notare le faccine ): avevo sbagliato il conteggio delle "inversioni" (si dice così?) nella configurazione di partenza mentre erano corretti i conteggi delle altre, di conseguenza ho invertito il risultato.
L'errore è consistito nello scambiare l'otto con il sei cioè $(7*6)/2$ invece che $(7*8)/2$.
Mi sembrava superfluo mettere il "diviso due"

Cordialmente, Alex

[3m0o]

Non ho usato un carattere più piccolo, ma se noti c'è un [ / spoiler ] di troppo, ma se faccio modifica il messaggio per eliminarlo, quello spoiler di troppo non esiste, i don't know why....
Edit: come puoi notare se metto solo lo spoiler finale mi diminuisce il carattere.
infatti c'è scritto un [ / spoiler ] tutto attaccato dopo me lo diminuisce [/spoiler] infatti qui c'è uno spoiler ....

Non so come si dica "inversioni" in italiano, sono la persona sbagliata a cui chiedere
Ma a dire il vero non ho nemmeno troppo capito da dove salta fuori quel
\( 42/2 \) e quel \(56/2 \)

[axpgn]

Misteri del Forum

Osservando la prima configurazione, si può notare che il $2$ ha sette inversioni, il $4$ ne ha sei, ecc. quindi $(7*6)/2=21$ sbagliando

Cordialmente, Alex

[Super Squirrel]

"Super Squirrel":Io ne conto rispettivamente $0$, $105$, $36$, $4$, $28$ e $12$.

Ogni configurazione possibile deve avere un numero pari di coppie disordinate. Quindi quella impossibile è la configurazione numero 2.

Non ricordo adesso la dimostrazione, lessi qualcosa tempo fa per implementare il gioco del 15 in C.