di Jacopo Garlasco
Una piccola sfida per matematici esperti di combinatoria ed invarianti:
ho in casa una vecchia dama cinese molto particolare, che vi mostro in fotografia qui sotto. Gioca una sola persona e le regole sono molto semplici:
1) Si parte da una scacchiera come quella qui sotto, dove ogni casella ha una pedina.
2) Si toglie una pedina da una casella a piacimento: nella foto qui sotto ho tolto quella centrale. Per comodità numero le caselle come coordinate cartesiane: ad esempio, quella centrale è (0,0), quella immediatamente a destra è (1,0), etc.
3) L’unica mossa consentita è prendere una pedina e mangiarne un’altra saltando nel posto successivo (a condizione che questo sia libero): ad esempio, in figura, la pedina (2,0) può saltare nella casella (0,0) e mangiare la (1,0), con quest’ultima che esce definitivamente di scena.
4) Il giocatore vince se e solo se riesce a rimanere alla fine con una sola pedina.Fin qui nessun problema, perché le prime volte non è facilissimo (specie da alcune posizioni di partenza) ma dopo svariati tentativi si giunge facilmente alla conclusione che è possibile vincere da qualunque posizione lasciata libera in partenza.Tuttavia la posizione di arrivo della pedina vincente può non essere sempre la stessa, anche a parità di posizione iniziale di partenza. Provando e riprovando, però, ho notato che in tutti i casi (in realtà ho fatto tante prove, ma non certo un numero statisticamente molto significativo) sussiste una relazione abbastanza interessante.
Scelgo una diagonale a 45° (non importa in quale senso) e coloro tutte le caselle della diagonale con la stessa tinta (e.g. rosso), eventualmente proseguendo anche nelle caselle immaginarie dove c’è il legno (per quanto riguarda i bracci della croce). Poi scendo verticalmente di 1 e faccio la stessa cosa con un’altra tinta (e.g. verde) e proseguo così, colorando tutta la scacchiera. Ebbene, in tutti i casi che ho analizzato nei miei break serali, se si toglie all’inizio una pedina da una casella rossa, qualora si riesca a vincere si finisce sempre su un’altra casella rossa, e così identicamente per gli altri due colori.Come provare a dare una dimostrazione? (Va detto, comunque, che potrebbe anche uscire un controesempio, il che è plausibile perché è un’ipotesi molto curiosa…)
3) L’unica mossa consentita è prendere una pedina e mangiarne un’altra saltando nel posto successivo (a condizione che questo sia libero): ad esempio, in figura, la pedina (2,0) può saltare nella casella (0,0) e mangiare la (1,0), con quest’ultima che esce definitivamente di scena.
4) Il giocatore vince se e solo se riesce a rimanere alla fine con una sola pedina.Fin qui nessun problema, perché le prime volte non è facilissimo (specie da alcune posizioni di partenza) ma dopo svariati tentativi si giunge facilmente alla conclusione che è possibile vincere da qualunque posizione lasciata libera in partenza.Tuttavia la posizione di arrivo della pedina vincente può non essere sempre la stessa, anche a parità di posizione iniziale di partenza. Provando e riprovando, però, ho notato che in tutti i casi (in realtà ho fatto tante prove, ma non certo un numero statisticamente molto significativo) sussiste una relazione abbastanza interessante.
Scelgo una diagonale a 45° (non importa in quale senso) e coloro tutte le caselle della diagonale con la stessa tinta (e.g. rosso), eventualmente proseguendo anche nelle caselle immaginarie dove c’è il legno (per quanto riguarda i bracci della croce). Poi scendo verticalmente di 1 e faccio la stessa cosa con un’altra tinta (e.g. verde) e proseguo così, colorando tutta la scacchiera. Ebbene, in tutti i casi che ho analizzato nei miei break serali, se si toglie all’inizio una pedina da una casella rossa, qualora si riesca a vincere si finisce sempre su un’altra casella rossa, e così identicamente per gli altri due colori.Come provare a dare una dimostrazione? (Va detto, comunque, che potrebbe anche uscire un controesempio, il che è plausibile perché è un’ipotesi molto curiosa…)
-
Cesco Reale Aaaah, eresia!! Come dama cinese?? Quello è un Solitaire, versione inglese ! Comunque non mi sembra chiarissimo, quanti colori usi?
- Alessio Palmero Aprosio Si potrebbe iniziare con un metodo Monte Carlo per vedere innanzi tutto se troviamo il contro esempio. Poi immagino che si possa ragionare sulla parità. In effetti sarebbe utile capire quanti colori usi
- Maurizio De Leo Se i colori sono due, e quindi stai sostanzialmente colorando le caselle come una scacchiera rossa e verde, la congettura mi sembra falsa. Partiamo dal fatto che la pedina che salta non cambia mai colore di casella. Le ultime due pedine saranno sempre adiacenti, quindi di due colori diversi. Ma tu puoi decidere di saltare la rossa con la verde (e quindi terminare sul verde) o viceversa (terminando sul rosso)
- Alessio Palmero Aprosio Quindi i colori sono per forza tre (altrimenti per il ragionamento di Maurizio si può scegliere un colore tra due diversi all’ultima mossa)
- Fabio Marconida come l’ha scritto i colori dovrebbero essere tanti quanti le diagonali (poiché dice che prendi una diagonale e la colori, poi vai giù di 1 e la colori di un colore diverso e così via), ma in questo caso, per il ragionamento di maurizio, non funziona
- Jacopo Garlasco No, scusate! I colori sono tre, mi ero dimenticato di scriverlo. Coloro procedendo in ordine, ad esempio rosso, verde, blu, rosso, verde, blu… secondo la procedura esposta sopra! Ma spero che la mia congettura non sia un’eresia come il nome di “dama cinese”…
- Maurizio De Leo Con tre colori funziona sempre. Assegniamo i valori 1,2 e 3 alle caselle rosse,verdi e blu con una pedina e assegniamo il valore 0 ad una casella vuota di qualsiasi colore. La somma dei valori (cardinalità) a scacchiera piena è 66. Togliendo una pedina verde la cardinalità diventa 64. Possiamo vedere che ognuno dei sei salti possibili (rosso salta verde e arriva su blu, rosso salta blu e arriva su verde, ecc.) cambia la cardinalità di uno dei seguenti valori: 0, -2, -4. Quindi la cardinalità finale deve essere pari. L’unica possibilità è che sia 2, ossia l’ultima pedina è sul verde.
Possiamo ripetere il ragionamento altre due volte riassegnando i numeri e togliendo sempre la pedina del colore che corrisponde al 2. La cardinalità finale sarà sempre due (ho riconfermato il valore iniziale e i possibili salti) e l’ultima pedina rimasta sarà sempre sul colore che abbiamo tolto.
Poiché le diagonali possono essere anche nell’altro senso, occorre fare l’intersezione delle soluzioni per trovare che le possibili configurazioni finali sono a coordinate 3k, 3k, con k in Z (l’origine è il buco iniziale).
Questo peró non dimostra l’esistenza di una soluzione, ci dice solo dove non può essere (cioé in tutti i posti diversi da 3k,3k). Ora, data una configurazione arbitraria di n pedine su tavoliere infinito, come si possono predire le configurazioni minime finali ?
Solo una piccola precisazione. Le coordinate finali sono 3k, 3j, con k,j appartenenti a Z. Ad esempio 0, 6 è una soluzione.
ah si certo, mia sbadataggine, grazie.
Sul problema generalizzato non riesco a fare osservazioni particolari. L’unica cosa che si riesce a dimostrare è che l’area del dominio iniziale deve essere minore o uguale del quadrato del numero di pedine iniziali per poter arrivare ad una singola pedina. L’area del dominio iniziale in caselle è definita (Xmax-Xmin-Xmax+1)*(Ymax-Ymin+1).