Divertente problema della S.Anna
Salve, stavo guardando i test della S.Anna ed ho trovato un problema molto simpatico 
Il testo è questo:
Si consideri il gioco seguente: 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 già occupate in precedenza (sia da A
che da B). Perde chi non riesce più a muovere la moneta in
una casella ammissibile.
Determinare, in funzione del numero n, quale tra i 2
giocatori ha una strategia vincente.
Io pensavo: vince chi riesce a lasciare sempre ai lati della pedina un numero pari di caselle di distanza dal bordo sia orizzontalmente che verticalmente, infatti dopo un numero pari di mosse sarà di nuovo il proprio turno, quindi se si prosegue sempre nello stesso verso si ha la possibilità di giungere a toccare il bordo e,se non ci sono più altre caselle, di vincere.
Bisogna però analizzare due casi, uno in cui n sia dispari quindi \(\ n=2k+1 \), in questo caso è sicuro che vinca B, perchè alla prima mossa A, sia se muove orizzontalmente che verticalmente, lascerà nel verso del moto \(\ 2k-1 \) caselle, numero dispari. Consideriamo che A si sia mosso orizzontalmente, se B prosegue orizzontalmente avrà numero pari di caselle libere in tutti i versi possibili per il moto, continua orizzontalmente finchè A non cambierà e muoverà verticalmente (cosa che è costretto a fare perchè è comunque B che giunge al bordo)lasciando \(\ 2k-1 \) caselle verticali, quindi B prosegue verticalmente ottenendo ai lati un numero pari. Iterando il procedimento B, per vincere, dovrà sempre muoversi nel verso in cui A si sarà mosso precedentemente, infatti così ha la certezza di lasciare ai lati un numero pari di caselle assicurandosi l'ultima mossa quando non ci saranno più caselle possibili su cui muoversi.
Lo stesso metodo è utile se A parte verticalmente, basta notare la simmetria che si ha ruotando la scacchiera di 90°
Se \(\ n=2k \) A potrà vincere giocando in modo opportuno, dopo la prima mossa lascerà un numero pari di caselle nel senso in cui si è mosso e un numero dispari nell'altro. Consideriamo sempre che A parta orizzontalmente, se B prosegue orizzontalmente A farà lo stesso finchè B non muoverà verticalmente (cosa che è costretto a fare ad ogni modo perchè è A a raggiungere il bordo), e avrà verso il basso numero pari di caselle, a quel punto la riga su cui si trova la pedina sarà divisa in due, da una parte un numero pari di caselle e dall'altra vi è un numero dispari, A deve proseguire orizzontalmente nella direzione in cui ci sono caselle dispari, così si assicura il bordo da tutti i lati. Quindi ogni volta che B cambia verso A dovrà cambiarlo nuovamente assicurandosi di dirigersi dove ci sono caselle dispari, altrimenti regala la vittoria a B.
Come prima si può vedere la simmetria ruotando la scacchiera di 90° e quindi il procedimento sarà lo stesso se A parte verticalmente.
Scusate se ho scritto in modo confusionario, se trovate qualche falla nella strategia ditemelo
Il testo è questo:
Si consideri il gioco seguente: 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 già occupate in precedenza (sia da A
che da B). Perde chi non riesce più a muovere la moneta in
una casella ammissibile.
Determinare, in funzione del numero n, quale tra i 2
giocatori ha una strategia vincente.
Io pensavo: vince chi riesce a lasciare sempre ai lati della pedina un numero pari di caselle di distanza dal bordo sia orizzontalmente che verticalmente, infatti dopo un numero pari di mosse sarà di nuovo il proprio turno, quindi se si prosegue sempre nello stesso verso si ha la possibilità di giungere a toccare il bordo e,se non ci sono più altre caselle, di vincere.
Bisogna però analizzare due casi, uno in cui n sia dispari quindi \(\ n=2k+1 \), in questo caso è sicuro che vinca B, perchè alla prima mossa A, sia se muove orizzontalmente che verticalmente, lascerà nel verso del moto \(\ 2k-1 \) caselle, numero dispari. Consideriamo che A si sia mosso orizzontalmente, se B prosegue orizzontalmente avrà numero pari di caselle libere in tutti i versi possibili per il moto, continua orizzontalmente finchè A non cambierà e muoverà verticalmente (cosa che è costretto a fare perchè è comunque B che giunge al bordo)lasciando \(\ 2k-1 \) caselle verticali, quindi B prosegue verticalmente ottenendo ai lati un numero pari. Iterando il procedimento B, per vincere, dovrà sempre muoversi nel verso in cui A si sarà mosso precedentemente, infatti così ha la certezza di lasciare ai lati un numero pari di caselle assicurandosi l'ultima mossa quando non ci saranno più caselle possibili su cui muoversi.
Lo stesso metodo è utile se A parte verticalmente, basta notare la simmetria che si ha ruotando la scacchiera di 90°
Se \(\ n=2k \) A potrà vincere giocando in modo opportuno, dopo la prima mossa lascerà un numero pari di caselle nel senso in cui si è mosso e un numero dispari nell'altro. Consideriamo sempre che A parta orizzontalmente, se B prosegue orizzontalmente A farà lo stesso finchè B non muoverà verticalmente (cosa che è costretto a fare ad ogni modo perchè è A a raggiungere il bordo), e avrà verso il basso numero pari di caselle, a quel punto la riga su cui si trova la pedina sarà divisa in due, da una parte un numero pari di caselle e dall'altra vi è un numero dispari, A deve proseguire orizzontalmente nella direzione in cui ci sono caselle dispari, così si assicura il bordo da tutti i lati. Quindi ogni volta che B cambia verso A dovrà cambiarlo nuovamente assicurandosi di dirigersi dove ci sono caselle dispari, altrimenti regala la vittoria a B.
Come prima si può vedere la simmetria ruotando la scacchiera di 90° e quindi il procedimento sarà lo stesso se A parte verticalmente.
Scusate se ho scritto in modo confusionario, se trovate qualche falla nella strategia ditemelo
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo