[C] Giuoco con punti e circonferenza

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

Continua l\'invasione dei problemi off topic di matematica olimpica. Si salvi chi può!!
 
 Su una circonferenza vi sono 2004 punti, e 2 amici fanno il seguente giuoco. A turno, ognuno unisce con un segmento 2 punti della circonferenza a sua scelta (purché non siano già uniti). Il giuoco finisce quando ogni punto è collegato ad almeno un altro punto, ed il vincitore è colui che ha fatto l\'ultima mossa. Chi ha una strategia vincente? Quello che inizia a giocare, o il secondo?

jim · Messaggio da **jim** » 01 gen 1970, 01:33

Premettendo che non sono molto pratico con la simbologia matematica, faccio lo stesso un tentativo:
 Il numero dei segmenti totali che si devono tracciare ulla circonferenza è dato da: sum(1; 2004-1)= sum(1; 2003). Ora, la sommatoria di un numero n può essere un numero pari o dispari: è pari quando n V n+1 è divisibile per 4.
 2003 non è divisibile per 4, ma 2003+1=2004 sì. Sappiamo quindi che la sommatoria dei numeri da 1 a 2003 (cioè (2003*2004)/2) è pari. Dal momento che vince chi fa l\'ultima mossa, essendo questa pari, vince chi parte per secondo, le cui mosse sono tutte in posizione pari.

gip · Messaggio da **gip** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-11 15:09, MindFlyer wrote:
 Continua l\'invasione dei problemi off topic di matematica olimpica. Si salvi chi può!!
 
 Su una circonferenza vi sono 2004 punti, e 2 amici fanno il seguente giuoco. A turno, ognuno unisce con un segmento 2 punti della circonferenza a sua scelta (purché non siano già uniti). Il giuoco finisce quando ogni punto è collegato ad almeno un altro punto, ed il vincitore è colui che ha fatto l\'ultima mossa. Chi ha una strategia vincente? Quello che inizia a giocare, o il secondo?
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 
 Per vincere bisogna trovarsi nella situazione in cui vi sono 1 o 2 punti ancora non toccati da segmenti, quindi si assicura la vittoria chi lascia l\'avversario con 3 punti scollegati e senza la possibilita\' di tracciare segmenti che congiungano i punti gia\' toccati in precedenza.
 
 Quando il numero t di segmenti tracciabili prima di tangere gli ultimi 3 punti e\' pari, vince il secondo giocatore, altrimenti il primo.
 
 Se sulla circonferenza ci sono n punti, t e\' dato dal coefficiente binomiale (n-3 su 2), pari a (n-3)*(n-4)/2 ; questo valore e\' dispari per n congruo a 1 o 2 (mod 4) e pari per n congruo a 3 o 0.
 
 Siccome 2004 e\' congruo a 0 (mod 4) vince il secondo giocatore.
 
 Ciao
 Marino
 
 Edit: D\'oh!!! [ Questo Messaggio è stato Modificato da: gip il 11-12-2004 18:48 ]

gip · Messaggio da **gip** » 01 gen 1970, 01:33

Forse e\' solo per giustificarmi per essere stato battuto sul tempo, ma non mi pare che la soluzione di jim sia corretta, dal momento che \"il giuoco finisce quando ogni punto è collegato ad almeno un altro punto\", cosa che avviene sempre prima che siano tracciati tutti i possibili segmenti.
 
 A questo proposito propongo una versione del gioco leggermente modificata: vince chi traccia l\'ultimo segmento di modo che da ogni punto sia possibile raggiungerne ogni altro tramite un percorso di segmenti (ossia in modo da rendere il grafo connesso).
 
 Ciao
 Marino <IMG SRC="images/forum/icons/icon_wink.gif">

jim · Messaggio da **jim** » 01 gen 1970, 01:33

Hai ragione, Gip: nella fretta di rispondere non ho letto \"almeno\" e l\'ho svolto come se ogni punto dovesse essere collegato ad ogni altro punto. Mi sono accorto dell\'errore mentre stavo cenando, e non ho avuto il tempo di scrivere la soluzione esatta perchè tu mi hai preceduto...
 La tua nuova versione dell\'esercizio, invece, non ho la più pallida idea di come risolverla.

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-11 19:02, gip wrote:
 A questo proposito propongo una versione del gioco leggermente modificata: vince chi traccia l\'ultimo segmento di modo che da ogni punto sia possibile raggiungerne ogni altro tramite un percorso di segmenti (ossia in modo da rendere il grafo connesso).
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Ok. Io ci sto. 2004 p.ti numerati da 1 a 2004. Comincio io. Congiungo 1 e 2.
 
 Ciao. M.[addsig]

ReKaio · Messaggio da **ReKaio** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 Ok. Io ci sto. 2004 p.ti numerati da 1 a 2004. Comincio io. Congiungo 1 e 2.
 
 Ciao. M
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 uhm... dimostrazione per autorevolezza.. ha scelto di giocare per primo, quindi esiste una strategia vincente per chi inizia. cvd

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-12-14 09:38, ReKaio wrote:
 uhm... dimostrazione per autorevolezza.. ha scelto di giocare per primo, quindi esiste una strategia vincente per chi inizia. cvd
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Lol!!
 
 Beh, la tesi è vera, ma temo che nel tuo ragionamento manchi la verifica di un\'ipotesi cruciale: per poter applicare il Principio di Autorevolezza, occorre verificare che l\'Autorità citata goda di sufficiente autorevolezza. Ipotesi che, nel nostro caso, in tutta onestà, non mi pare verificata...
 <IMG SRC="images/forum/icons/icon_wink.gif">