Vi ricordate il giochino del 15? No? E che campate a fare? Ripassino!
(a) Perchè non è possibile risolvere il gioco partendo dalla configurazione con 14 e 15 scambiati?
(a') Esiste un modo di rispondere alla domanda (a) colorando?
(b) Trovare una condizione necessaria e sufficiente sulla disposizione iniziale delle tessere affinchè il gioco sia risolubile.
(b') Esiste un modo di rispondere (parzialmente) alla domanda (b) colorando?
Dal glossario con furore...
Dal glossario con furore...
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Gioco 15 generalizzato
Ci stavo pensando giusto oggi senza aver mai visto il messaggio e sono riuscito a trovare una generalizzazione per il gioco del 15.
Sia dato un grafo finito, connesso, con n nodi, con almeno un ciclo e con le seguenti proprieta':
- tutti i cicli hanno lunghezza pari
- ogni nodo del grafo appartiene ad almeno un ciclo del grafo
- se il grafo ha piu' di un ciclo allora ogni ciclo del grafo ha almeno un arco in comune con almeno un altro ciclo del grafo
Si assegni in modo arbitrario un numero intero da 1 a n inclusi ad ogni nodo del grafo e si definiscano i numeri associati ai nodi $ a_i \in \{1, \ldots, n \} $ tali che ogni elemento dell'insieme $ \{1, \ldots, n \} $ e' associato ad uno ed un solo nodo del grafo
Si gioca nel seguente modo: se il nodo i e' tale che $ a_i = n $ e' possibile scambiare i numeri associati al nodo i e ad un qualsiasi nodo ad esso collegato con un arco
Potete verificare che il gioco del 15 puo' essere rappresentato con un grafo del genere: ci sono 4*4 nodi ad ognuno dei quali e' associato un numero da 1 a 16 (16 e' il quadratino vuoto)
Il gioco viene vinto se ad un certo punto si ottiene $ a_i=i \: \forall \: 1 \leq i \leq n $
Si definisca ora l'errore del nodo i come $ e_i=|k: i<k \leq n \wedge a_k<a_i \| $ e si definisca l'errore totale come $ E=\sum_{i=1}^n e_i $. Sia poi d la parita' della lunghezza del cammino dal nodo j a cui e' associato il numero n al nodo n (ed e' qui che serve l'ipotesi della parita' della lunghezza dei cicli: infatti in questo modo e' possibile colorare ogni nodo del grafo in bianco o in nero in modo che 2 nodi uniti da un arco abbiano colori distinti: se il nodo j ha lo stesso colore del nodo n allora d e' 0, se no e' 1). Dopo tutti i preliminari ecco la tesi: e' possibile da una situazione arrivare a vincere il gioco se e solo se in quella situazione $ E+d \equiv 0 \pmod{2} $
Le altre 2 condizioni dell'ipotesi sul grafo servivano semplicemente per assicurarsi che ogni numero possa essere spostato in un qualsiasi nodo del grafo
Nella situazione finale, quando si vince il gioco, si ha E=d=E+d=0. Bisogna provare, per la condizione necessaria, che $ E+d \pmod{2} $ e' un invariante. d varia sempre poiche' n si sposta continuamente da un nodo bianco ad uno nero e viceversa, bisogna solo capire come varia E. Sia j il nodo tale che $ a_j=n $ e sia i un nodo collegato con un arco al nodo j e vogliamo cambiare tra loro i numeri $ a_i $ e n associati ai nodi. Se tra i e j ci sono un numero pari di numeri allora il "contributo" ad E dato dal numero $ a_i $ non cambia in parita' in quanto i numeri $ a_k $ con k tra i e j esclusi, che cambiano il valore di E se si sposta il numero $ a_i $ sono in numero pari minori e maggiori di $ a_i $, oppure in numero dispari minori e maggiori di $ a_i $, mentre il contributo dato da n cambia di parita' perche' c'e' da considerare il numero $ a_i $, che e' sempre <n. Viceversa se tra i e j ci sono un numero dispari di numeri, ma allora anche E cambia modulo 2, e quindi d+E e' invariante
P.S. Scusate se non avete capito qualcosa, e' che qui non ho internet a casa e scrivo un po' di fretta da un internet point. Uno di questi giorni faccio una spiegazione piu' dettagliata.
Il succo e' che se si costruisce il grafo associato al gioco del 15 e si invertono il 14 e il 15 si ha E=1 e d=0, quindi non si puo' arrivare a vincere
Sia dato un grafo finito, connesso, con n nodi, con almeno un ciclo e con le seguenti proprieta':
- tutti i cicli hanno lunghezza pari
- ogni nodo del grafo appartiene ad almeno un ciclo del grafo
- se il grafo ha piu' di un ciclo allora ogni ciclo del grafo ha almeno un arco in comune con almeno un altro ciclo del grafo
Si assegni in modo arbitrario un numero intero da 1 a n inclusi ad ogni nodo del grafo e si definiscano i numeri associati ai nodi $ a_i \in \{1, \ldots, n \} $ tali che ogni elemento dell'insieme $ \{1, \ldots, n \} $ e' associato ad uno ed un solo nodo del grafo
Si gioca nel seguente modo: se il nodo i e' tale che $ a_i = n $ e' possibile scambiare i numeri associati al nodo i e ad un qualsiasi nodo ad esso collegato con un arco
Potete verificare che il gioco del 15 puo' essere rappresentato con un grafo del genere: ci sono 4*4 nodi ad ognuno dei quali e' associato un numero da 1 a 16 (16 e' il quadratino vuoto)
Il gioco viene vinto se ad un certo punto si ottiene $ a_i=i \: \forall \: 1 \leq i \leq n $
Si definisca ora l'errore del nodo i come $ e_i=|k: i<k \leq n \wedge a_k<a_i \| $ e si definisca l'errore totale come $ E=\sum_{i=1}^n e_i $. Sia poi d la parita' della lunghezza del cammino dal nodo j a cui e' associato il numero n al nodo n (ed e' qui che serve l'ipotesi della parita' della lunghezza dei cicli: infatti in questo modo e' possibile colorare ogni nodo del grafo in bianco o in nero in modo che 2 nodi uniti da un arco abbiano colori distinti: se il nodo j ha lo stesso colore del nodo n allora d e' 0, se no e' 1). Dopo tutti i preliminari ecco la tesi: e' possibile da una situazione arrivare a vincere il gioco se e solo se in quella situazione $ E+d \equiv 0 \pmod{2} $
Le altre 2 condizioni dell'ipotesi sul grafo servivano semplicemente per assicurarsi che ogni numero possa essere spostato in un qualsiasi nodo del grafo
Nella situazione finale, quando si vince il gioco, si ha E=d=E+d=0. Bisogna provare, per la condizione necessaria, che $ E+d \pmod{2} $ e' un invariante. d varia sempre poiche' n si sposta continuamente da un nodo bianco ad uno nero e viceversa, bisogna solo capire come varia E. Sia j il nodo tale che $ a_j=n $ e sia i un nodo collegato con un arco al nodo j e vogliamo cambiare tra loro i numeri $ a_i $ e n associati ai nodi. Se tra i e j ci sono un numero pari di numeri allora il "contributo" ad E dato dal numero $ a_i $ non cambia in parita' in quanto i numeri $ a_k $ con k tra i e j esclusi, che cambiano il valore di E se si sposta il numero $ a_i $ sono in numero pari minori e maggiori di $ a_i $, oppure in numero dispari minori e maggiori di $ a_i $, mentre il contributo dato da n cambia di parita' perche' c'e' da considerare il numero $ a_i $, che e' sempre <n. Viceversa se tra i e j ci sono un numero dispari di numeri, ma allora anche E cambia modulo 2, e quindi d+E e' invariante
P.S. Scusate se non avete capito qualcosa, e' che qui non ho internet a casa e scrivo un po' di fretta da un internet point. Uno di questi giorni faccio una spiegazione piu' dettagliata.
Il succo e' che se si costruisce il grafo associato al gioco del 15 e si invertono il 14 e il 15 si ha E=1 e d=0, quindi non si puo' arrivare a vincere
Presidente della commissione EATO per le IGO