Pagina 1 di 1
Scacchiera, vecchio SSSUP
Inviato: 05 set 2009, 21:51
da Albertopisa
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.
Inviato: 09 set 2009, 00:18
da kn
Anche se è facile era meglio metterlo in Combinatoria, l'habitat ideale di Alberto e Barbara (A e B sono solo le loro iniziali

)
Inviato: 03 apr 2010, 15:02
da Anlem
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.

Inviato: 05 apr 2010, 00:49
da kn
Anlem ha scritto:Una strategia vincente per B potrebbe essere quella di "copiare" la mossa fatta subito prima da A.
Non sempre puoi farlo

Carino il problema comunque, è un'ottima applicazione del principio di induzione! (piccolo hint

)
Inviato: 06 apr 2010, 19:11
da gian92
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...
Inviato: 10 apr 2010, 18:33
da Anlem
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)...
Non sono sicura che si possa sempre fare. Tu riesci a dimostrarlo?
Inviato: 11 apr 2010, 12:55
da gian92
Anlem ha scritto: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)...
Non sono sicura che si possa sempre fare. Tu riesci a dimostrarlo?
no non saprei come...però dovrebbe essere equivalente al problema...
o almeno implica la tesi del problema...non saprei se anche il contrario valga...
Inviato: 11 apr 2010, 13:17
da Sonner
gian92 ha scritto:per concludere bisogna dimostrare che indipendentemente dalle mosse di uno dei due, si può sempre colorare tutta la scacchiera.
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.
Inviato: 11 apr 2010, 15:06
da Anlem
Risolverlo equivarrebbe a risolvere il problema, solo che non so se sia vero.