OliForum Matematico

Questa è una generalizzazione di un problema dato all'ultimo test d'ammissione alla Scuola Sant'Anna.

I due giocatori A e B hanno una scacchiera rettangolare di lati n e m, ed una monetina posta inizialmente su una casella. Cominciando da A, a turno devono muovere la monetina su una casella adiacente a quella in cui si trova (adiacente=avente un lato in comune). Ma non possono muovere la monetina su una casella in cui è già stata in precedenza. Perde chi non può più muovere.

Dimostrare che se le caselle della scacchiera sono dispari, e la monetina si trova inizialmente su una casella dello stesso colore delle caselle ai vertici, allora B ha una strategia vincente. In caso contrario, ce l'ha A.

ok.... Work in progress allora...

Caro pi_greco_quadro, dovrei redarguirti per non aver capito nulla del problema.

Per prima cosa, "wlog" significa "senza perdita di generalità", e si usa quando ci si vuole ricondurre ad un unico caso di una dimostrazione. Perciò non ha senso che tu scriva che wlog la monetina si trova in una casella bianca, e poi faccia anche il caso in cui si trova su una nera!

Ma il vero problema è che la tua soluzione presenta parecchie carenze. Per esempio, non è affatto evidente (e nemmeno vero) che se un giocatore ha più caselle dove potrebbe trovarsi in un qualche futuro ed a qualche condizione, allora ha la strategia vincente. Se sei convinto di questa tesi quantomeno bizzarra, dovresti dimostrarla in modo opportuno.

Cancelliamo

Vedi, la tua soluzione continua ad avere lo stesso problema di fondo. Ed aggiungere terminologia (posizione di forza, sistema chiuso ) non aiuta di certo, ma anzi appesantisce la lettura. Insomma, se riscrivi una soluzione sbagliata o incompleta cambiando le parole, resta una soluzione sbagliata o incompleta.

Il problema è questo: come fai a dimostrare che se un giocatore può andare (in una qualche possibile partita) in un numero dispari di caselle, allora ha una strategia vincente? Dubito fortemente che sia vero (in generale è falsissimo, ma magari in questo gioco è vero!), ed anche se fosse vero sono praticamente certo che non ne esista una dimostrazione decente.

Ti consiglio di cambiare radicalmente approccio..

Mi si chiede una traccia di soluzione via mp. Penso sia più utile scrivere qui un suggerimento, anziché la traccia completa.

HINT: tassellare la scacchera con rettangolini 2x1.

Lascio giu' qualche idea riflettendo sull'hint che mi hai lasciato... nel caso in cui fosse giusta o sbagliata, ti invito comunque a commentare a piacere...

quindi se ho ben capito... con i rettangolini da te proposti posso tassellare una scacchiera che contenga un numero pari di caselle, mentre posso tassellare una scacchiera contenente un numero dispari di caselle se lascio al di fuori della tassellatura una casella dello stesso colore delle caselle ai vertici (che puo' essere una qualunque di questo colore)

Dimostro che un giocatore ha una strategia vincente se ogni volta che muove riesce a completare uno di questi rettangolini con cui abbiamo tassellato la scacchiera.

Quindi verifico che solo nella configurazione in cui le caselle siano dispari e la monetina si trovi su una casella dello stesso colore di quelle ai vertici, allora B riesce costantemente a completare uno dei rettangolini con cui abbiamo tassellato la scacchiera, mentre in ogni altro caso e' A ad avere questa possibilita'.

E' esatto quello che ho pensato? prima che mi avventuri ancora vorrei avere conferma.. grazie in anticipo

Ti dimostro che se il numero delle caselle è pari, allora a ha una strategia vincente:

Tassello la scacchiera con pezzi 2x1. Perché A vinca, è sufficiente che in ogni sua mossa "completi" il rettangolino su cui già si trova la pedina, di modo che sia sempre B a doversi muovere da un rettangolino ad un altro. Allora A può sempre muovere, e si arrva a un punto in cui B non può più muovere

E anche l'altro caso che mi è venuto ora (pensavo chissà che):

Se invece wlog ho una casella nera in più e si parte da quella, tassello come prima tutte le altre lasciandola scoperta. Ora è B che può fare il gioco che prima era di A.
...cazzo se era facile... pensa che all'esame l'ho lasciato bianco!

Esatto, la dimostrazione di Fabrizio del 1° punto è ineccepibile, ed è in 2 righe.
Il 2° caso è sostanzialmente corretto, anche se manca la dimostrazione che è possibile fare la tassellazione voluta comunque si scelga una casella iniziale nera.
Il 3° caso (caselle dispari e si parte da una bianca) è invece tutto da risolvere, a voi la parola!

visto che le mie deduzioni erano corrette... ringrazio mind per l'hint lasciato.. allora.....

Caso 3

La scacchiera con caselle dispari puo' essere tassellata supponendo che si lasci al di fuori della tassellatura una casella il cui colore e' uguale a quello delle caselle ai vertici. Dunque....
Supponiamo che le caselle ai vertici siano nere. Quindi noi sappiamo che le caselle nere soddisfano la seguente relazione rispetto alle bianche. Siano $ N $ e $ B $ i numeri di caselle bianche e nere rispettivamente, allora avremo $ N=B+1 $. Ma, poiche' comunque venga posizionato, un rettangolino $ 2 \mbox{x} 1 $ copre esattamente una casella bianca ed una casella nera, ricaviamo che il numero di caselle nere tassellate deve essere uguale a quello delle caselle bianche. Quindi se la casella lasciata vuota e' nera, allora la tassellatura e' possibile, qualunque essa sia.

quindi, se A parte da una casella che non sia nera, necessariamente si trova a muovere riuscendo continuamente a completare un rettangolino, e quindi ha una strategia vincente.

Al contrario se A muove da una casella nera, allora possiamo pensare che quella sia la casella lasciata vuota dalla tassellatura, quindi e' B in realta' in questo schema di gioco che riesce a completare i rettangolini ogni volta che muove.

Hai ragione mi ero dimenticato. (Forse la pizza calda può aver contribuito )

E' possibile tassellare la scacchiera in quel modo?
Si, e si vede facilmente: considero la riga e la colonna in cui è contenuta la casella nera di partenza. Le ricopro con i bimini (disposti per il lungo), questo è sempre possibile perché devono avere entrambe lunghezza dispari. I quattro rettangoli che rimagono sono di lati pari.

Giusto, Fabrizio.

pi_greco_quadro, manca anche per te la dimostrazione che esiste la tassellazione dei rettangoli dispari che lascia fuori una casella nera (vedi ultimo post di Fabrizio). Comunque questo era il caso 2, che era già risolto.

Il caso in cui A parte da una casella bianca è sostanzialmente giusto, anche se volendo fare le cose come si deve, bisognerebbe spendere 2 parole per osservare esplicitamente che B non può muovere nell'unica casella non tassellata (cosa che lascerebbe A senza risposte e non gli garantirebbe più di vincere!).

E arriva anche l'ultima parte

Se ho $ m \times n $ dispari e si parte dal bianco..
Di nuovo A ha una strategia vincente: è sufficiente che la prima casella nera su cui si muove sia quella esclusa dal tassellamento.
Allora A può fare sempre il solito gioco, tranne forse il caso in cui B muova sul nero accopiato col bianco iniziale... ma questo è impossibile perché è solo A che muove dal bianco al nero.

EDIT:
scusate mi ero perso gli ultimi passaggi

Sì, sostanzialmente giusto, Fabrizio.
Nota che aggiungi un'inutile complicazione quando dici che la prima mossa di A dev'essere nella casella non tassellata. La casella non tassellata può essere dove vuole, ed A muove sempre nello stesso modo (compresa la prima mossa!), ovvero completando i rettangolini 2x1 della tassellazione. In ogni caso, B non potrà mai muovere nella casella non tassellata perché è del colore opposto a quello in cui muove B.