II gara a squadre UNIMI- Quesito 4

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

II gara a squadre UNIMI- Quesito 4

Messaggio da Boll » 19 gen 2006, 15:56

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
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)

Igor
Messaggi: 108
Iscritto il: 01 gen 1970, 01:00

Messaggio da Igor » 19 gen 2006, 17:03

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 :D ) 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 $

Igor
Messaggi: 108
Iscritto il: 01 gen 1970, 01:00

Messaggio da Igor » 19 gen 2006, 17:09

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.

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 19 gen 2006, 17:12

Uhm, dopo la leggo bene, ma da quello che dici pare che con 6, ad esempio, non ci sia strategia, mentre mi parrebbe così...
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 19 gen 2006, 17:14

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
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)

Avatar utente
MASSO
Messaggi: 134
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza\Pisa

Messaggio da MASSO » 20 gen 2006, 18:49

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.

Rispondi