Newsgroup: it.hobby.enigmi
Titolo: Gioco del 14-15

(Sempre che il nome e' quello giusto..) e' un famoso rompicapo inventato
da Sam Loyd, consistente nell'ordinare 15 cubi numerati disposti casualmente
in un casellario 4x4 attraverso *soli* scorrimenti.
In letteratura si trova che per disposizioni casuali il rompicapo e' risolubile
solo nella meta' dei casi, per un discorso di parita', ma non ho mai visto la
dimostrazione rigorosa.
Chi ha un buon argomento a proposito ?

 ha scritto nel messaggio
news:3C4D98F5...@cclinf.polito.it...

Ho trovato un argomento un po' intricato: spero di riuscire a spiegarmi.
Iniziamo con una premessa:
Consideriamo un certo numero di caselle etichettate A,B,C...ecc., e
altrettante pedine con le stesse etichette.
Disponiamo arbitrariamente le pedine sulle caselle, per esempio:
Pedine  H D F B I N A C G E M L
Caselle A B C D E F G H I L M N
Considerato che sulla casella A c'è la pedina H, sulla H c'è la C, e così
via fino a tornare alla A, possiamo raggruppare idealmente le coppie
casella-pedina per formare dei *circuiti* chiusi (compresi eventuali
*circuiti* di una sola pedina, se questa si trova al posto giusto). Nel caso
in esempio abbiamo i tre circuiti:
HCFNLEIGA
AHCFNLEIG
DB
BD
M
M
Consideriamo il primo dei tre circuiti e invertiamo la posizione di due
pedine, per esempio N e G,
HCFGLEINA
AHCFNLEIG
poi riordiniamo le cose, e vediamo che il circuito si suddivide in due
circuiti nuovi:
HCFGA
AHCFG
LEIN
NLEI
Si vede facilmente che se invertiamo la posizione di due pedine appartenenti
allo stesso circuito, questo si suddivide in due, se invece invertiamo la
posizione di due pedine appartenenti a due circuiti diversi, questi si
fondono in un circuito unico. In sintesi, ad ogni inversione di una coppia
di pedine il numero totale di circuiti passa da pari a dispari o vv.
-----------
Passiamo ora al gioco del 15
Numeriamo le caselle della tavola da 1 a 16, disponiamo a piacere le 15
pedine, e ipotizziamo una pedina *virtuale* col numero 16 nella casella
rimasta vuota.
La disposizione delle pedine corrisponde a un certo numero di *circuiti*, al
limite 16 circuiti unitari a gioco concluso.
Ogni mossa lecita equivale all'inversione della pedina virtuale con una di
quelle adiacenti, e quindi per ogni mossa cambia la parità nel numero di
*circuiti*.
Pensiamo ora alla tavola come a una frazione di scacchiera, con la casella
16 bianca.
Ad ogni mossa lecita la pedina virtuale passa da una casa bianca a una nera
o vv.; a gioco concluso sarà in una casa bianca.
Riepilogando, a gioco finito avremo:
_16 circuiti;
_la pedina virtuale in casa bianca.
Se nella posizione iniziale la pedina virtuale è sul bianco, per finire il
gioco occorrono un numero pari di mosse, per cui i circuiti devono essere in
numero pari.
In sintesi, se nella posizione iniziale abbiamo:
_numero pari di circuiti e casella vuota bianca
oppure
_numero dispari di circuiti e casella vuota nera
il gioco riesce
nei due casi opposti il gioco non può riuscire.
-----------
In realtà la dimostrazione (ammesso che se ne sia capito qualcosa) mi sembra
ancora carente; infatti ho trovato condizioni necessarie, ma non ho
dimostrato che siano sufficienti; in altre parole ho dimostrato che nel 50%
dei casi il gioco non può riuscire, ma non che nel rimanente 50% riesca
sempre.
ciao
paolo