OliForum Matematico

Analizzare il seguente gioco tra due persone: dati $ n $ punti nel piano tali che a $ 3 $ a $ 3 $ non siano allineati, alternativamente i giocatori collegano con un segmento due punti non ancora collegati. Vince quel giocatore che per primo riesce a sistemare il suo segmento in modo che tutti i punti siano gli estremi di almeno un segmento. Per esempio se i punti fossero $ 5 $ il primo giocatore, se gioca correttamente, puµo garantirsi la vittoria collegando tra loro $ 2 $ vertici qualsiasi, il suo avversario ha due scelte: o collega fra loro $ 2 $ dei $ 3 $ vertici rimanenti o collega un vertice rimanente con uno dei due vertici giµa fra loro collegati. In ogni caso il primo giocatore al turno successivo vince collegando quel punto (o quei punti) che non sono stati ancora coinvolti, in modo tale che tutti i $ 5 $ punti iniziali sono vertici di almeno un segmento. Dire per quali valori di $ n $ il giocatore che inizia ha una strategia vincente

Dimostriamo che tutti gli $ n $ della forma $ 3k+2 $ permettono al giocatore iniziale di vincere.Abbiamo infatti che:

A)Con una mossa,un giocatore può diminuire il numero di vertici occupati di 1 o di 2(eccetto la prima mossa,in cui se ne occupano necessariamente 2)

B)Se un giocatore resta con tre vertici scoperti,perde.

Verfichiamo ora che con $ n $ della forma $ 3k+2 $ il giocatore iniziale(che ho il sospetto si chiami A ) ha una strategia vincente.Infatti alla prima mossa diminuisce di due il numero di vertici scoperti,di cui ne resteranno
dunque $ 3k $.Nelle mosse succesive,se il giocatore B occupa $ p $ vertici,egli ne occupa nel suo turno $ 3-p $.In questo modo il giocatore B si ritroverà alla fine con 3 vertici scoperti,e dunque perderà.

Adesso vediamo come per altri valori di $ n $ sia B ad avere una strategia vincente.

.Se $ n $ è della forma $ 3k $,il giocatore B vince per il metodo descritto in precedenza

.Se $ n $ è della forma $ 3k+1 $,il giocatore A alla prima mossa occupa 2 vertici.Alla mossa successiva B occupa altri due vertici.Il giocatore A resta dunque con $ 3k+1-4=3(k-1) $ vertici e quindi perde.

Da considerare a parte è il caso $ n=2 $,in cui non si può applicare il ragionamento fatto ma che permette comunque ad A di vincere collegando i due vertici alla prima mossa.

In giocatore iniziale ha dunque una strategia vincente per gli $ n $ della forma $ 3k+2 $,con $ k\in N $

Beh, potevo risparmiarmi un pò di parole osservando semplicemente che se un giocatore vince con un certo numero $ n $ di vertici,allora vince anche con $ n+3 $.Basta allora vedere che A vince con $ n=2 $ e che perde con $ n=3,4 $ per concludere.

Uhm, dopo la leggo bene, ma da quello che dici pare che con 6, ad esempio, non ci sia strategia, mentre mi parrebbe così...

Ho capito a cosa è dovuto, tu non consideri che due vertici già occupati, ma non ancora connessi fra loro, possano essere connessi tramite una mossa, invece, secondo il problema, è possibile

Dunque, è evidente che chi collega almeno uno degli ultimi tre punti ha perso, perciò lo farà solo se è obbligato e cioè se sono già stati posti tutti gli altri (n-3,2) segmenti; ergo per n congruo a 0 e -1 modulo 4, vince il secondo giocatore, negli altri casi vince il primo.