Si consideri il seguente gioco: su una scacchiera n x n si mette una moneta nella casella in alto a sinistra e due giocatori $ A $ e $ B $ muovono a turno, cominciando da $ A $, la moneta. Ogni mossa consiste nello spostare la moneta di una casella, in orizzontale oppure in verticale, evitando di occupare le caselle gia' occupate in precedenza (sia da $ A $ che da $ B $). Perde chi non riesce piu' a muovere la moneta in una casella ammissibile.
Determinare, in funzione di $ n $, quale tra i 2 giocatori ha una strategia vincente.
Scacchiera, vecchio SSSUP
)Provo a risolvere questo problema. Anche se non sono tanto convinta della mia soluzione.
Coloriamo le caselle alternativamente di bianco e di nero, a partire da quella in alto a sinistra che sarà nera.
E' evidente che ogni mossa di A consiste nello spostare la moneta da una casella nera ad una bianca, mentre ogni mossa di B consiste nello spostare la moneta da una casella bianca ad una nera.
Se n è dispari abbiamo una casella nera in più rispetto a quelle bianche. Quindi B vince se vengono occupate tutte le caselle o se viene lasciato vuoto un numero pari di caselle.
Se la differenza tra il numero degli spostamenti verso destra e il numero degli spostamenti verso sinistra e la differenza tra il numero di spostamenti verso l'alto e il numero di spostamenti verso il basso sono pari, B vince perchè resta vuoto un numero pari di caselle.
Una strategia vincente per B potrebbe essere quella di "copiare" la mossa fatta subito prima da A. In questo modo ci sarebbe un numero pari di spostamenti di ciascun tipo e quindi anche le differenza sarebbero pari.
Rimando alla prossima puntata il caso in cui n è pari.
Coloriamo le caselle alternativamente di bianco e di nero, a partire da quella in alto a sinistra che sarà nera.
E' evidente che ogni mossa di A consiste nello spostare la moneta da una casella nera ad una bianca, mentre ogni mossa di B consiste nello spostare la moneta da una casella bianca ad una nera.
Se n è dispari abbiamo una casella nera in più rispetto a quelle bianche. Quindi B vince se vengono occupate tutte le caselle o se viene lasciato vuoto un numero pari di caselle.
Se la differenza tra il numero degli spostamenti verso destra e il numero degli spostamenti verso sinistra e la differenza tra il numero di spostamenti verso l'alto e il numero di spostamenti verso il basso sono pari, B vince perchè resta vuoto un numero pari di caselle.
Una strategia vincente per B potrebbe essere quella di "copiare" la mossa fatta subito prima da A. In questo modo ci sarebbe un numero pari di spostamenti di ciascun tipo e quindi anche le differenza sarebbero pari.
Rimando alla prossima puntata il caso in cui n è pari.
Non sempre puoi farloAnlem ha scritto:Una strategia vincente per B potrebbe essere quella di "copiare" la mossa fatta subito prima da A.
Carino il problema comunque, è un'ottima applicazione del principio di induzione! (piccolo hint
)Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
per concludere bisogna dimostrare che indipendentemente dalle mosse di uno dei due, si può sempre colorare tutta la scacchiera (diciamo che quando alberto va su una casella la colora bianca e quando ci va barbara nera)...
per induzione sul lato della scacchiera..non saprei come farlo
in pratica se abbiamo una scacchiera come quella degli scacchi nXn (perchè di quel tipo viene colorandola in questo modo) bisogna dimostrare che si può sempre aggiungere una riga e una colonna...
per induzione sul lato della scacchiera..non saprei come farlo
in pratica se abbiamo una scacchiera come quella degli scacchi nXn (perchè di quel tipo viene colorandola in questo modo) bisogna dimostrare che si può sempre aggiungere una riga e una colonna...
Non sono sicura che si possa sempre fare. Tu riesci a dimostrarlo?gian92 ha scritto:per concludere bisogna dimostrare che indipendentemente dalle mosse di uno dei due, si può sempre colorare tutta la scacchiera (diciamo che quando alberto va su una casella la colora bianca e quando ci va barbara nera)...
no non saprei come...però dovrebbe essere equivalente al problema...Anlem ha scritto:Non sono sicura che si possa sempre fare. Tu riesci a dimostrarlo?gian92 ha scritto:per concludere bisogna dimostrare che indipendentemente dalle mosse di uno dei due, si può sempre colorare tutta la scacchiera (diciamo che quando alberto va su una casella la colora bianca e quando ci va barbara nera)...
o almeno implica la tesi del problema...non saprei se anche il contrario valga...
Forse non ho capito cosa intendi ma ad esempio, in una scacchiera 4x4, con la sequenza "giù,giù,destra,destra,su,su,sinistra,giù" la monetina non si può più muovere ma non è passata per tutte le caselle.gian92 ha scritto:per concludere bisogna dimostrare che indipendentemente dalle mosse di uno dei due, si può sempre colorare tutta la scacchiera.