Sono un paio di giorni che mi sto scervellando su questo quesito. Mi vengono in mente varie idee ma non riesco a giungere ad una conclusione.
Vi posto il problema:
"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. "
Vi descrivo un pò le idee che mi sono venute ed il ragionamento che ho effettuato:
Ho analizzato i primi n casi con n=1,2,3,4,5
Sembra che nel caso in cui n sia pari sia il giocatore A a vincere (quello che muove per primo) mentre nel secondo caso sia il giocatore B.
In particolare con n pari il nuomero di caselle su cui può muovere il giocatore A è maggiore di uno rispetto a quelle su cui può muovere il giocatore B (ad esempio se n=2 e la prima casella in alto a sinistra è nera A muoverà solo su caselle bianche che sono 2 mentre la nera è solo 1). è facilmente dimostrabile che se si coprisse tutte le caselle della scacchiera vincerebbe A nel caso in cui n fosse pari e B nel caso in cui n sia dispari. Dimostrare quindi che vi è un modo attraverso il quale uno dei due giocatori obbliga l' altro a muovere in determinate caselle in modo tale da occupare tutta la scacchiera determinerebbe la strategia vincente. Ho provato in vari modi ma non riesco a dimostrare questo punto che mi sembra la miglior idea avuta finora.
Inoltre ho pensato che se nella scacchiera non fossero ricoperti un numero pari di caselle il risultato resterebbe invariato (ad esempio in una casella 4x4 se le 4 in alto a destra non fossero occupate mentre tutte le altre si il vincitore sarebbe sempre A)
Un' altra idea è che una volta raggiunto il lato di destra e quello in basso la scacchiera risultà "spaccata" in due blocchi quindi chi si troverà a muovere in questo caso sceglierà da che parte andare e quindi quale parte della scacchiera non occupare.
Queste sono alcune delle idee che mi sono venute.
Qualcuno può darmi qualche dritta o qualche suggerimento?
