Scacchiera, vecchio SSSUP

Giochini matematici elementari ma non olimpici.
Rispondi
Albertopisa
Messaggi: 18
Iscritto il: 04 dic 2008, 22:09

Scacchiera, vecchio SSSUP

Messaggio 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.
Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio 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 :twisted: )
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
Anlem
Messaggi: 195
Iscritto il: 26 giu 2006, 08:58
Località: Pavia

Messaggio 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. :)
Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio 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 :wink: )
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
Avatar utente
gian92
Messaggi: 558
Iscritto il: 12 nov 2007, 13:11
Località: roma

Messaggio 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...
Anlem
Messaggi: 195
Iscritto il: 26 giu 2006, 08:58
Località: Pavia

Messaggio 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?
Avatar utente
gian92
Messaggi: 558
Iscritto il: 12 nov 2007, 13:11
Località: roma

Messaggio 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...
Sonner
Messaggi: 364
Iscritto il: 12 feb 2009, 16:02
Località: Susa (TO)

Messaggio 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.
Anlem
Messaggi: 195
Iscritto il: 26 giu 2006, 08:58
Località: Pavia

Messaggio da Anlem »

Risolverlo equivarrebbe a risolvere il problema, solo che non so se sia vero.
Rispondi