[C] Giuoco con punti e circonferenza

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
MindFlyer

Messaggio da MindFlyer » 01 gen 1970, 01:33

Continua l\'invasione dei problemi off topic di matematica olimpica. Si salvi chi può!!
<BR>
<BR><!-- BBCode Start --><B>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?</B><!-- BBCode End -->

Avatar utente
jim
Messaggi: 125
Iscritto il: 01 gen 1970, 01:00
Località: Asti

Messaggio da jim » 01 gen 1970, 01:33

Premettendo che non sono molto pratico con la simbologia matematica, faccio lo stesso un tentativo:
<BR>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.
<BR>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.
<BR>

Avatar utente
gip
Messaggi: 86
Iscritto il: 01 gen 1970, 01:00
Località: Pisa, Scuola Superiore Sant'Anna
Contatta:

Messaggio da gip » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-12-11 15:09, MindFlyer wrote:
<BR>Continua l\'invasione dei problemi off topic di matematica olimpica. Si salvi chi può!!
<BR>
<BR><!-- BBCode Start --><B>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?</B><!-- BBCode End -->
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>
<BR>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.
<BR>
<BR>Quando il numero t di segmenti tracciabili prima di tangere gli ultimi 3 punti e\' pari, vince il secondo giocatore, altrimenti il primo.
<BR>
<BR>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.
<BR>
<BR>Siccome 2004 e\' congruo a 0 (mod 4) vince il secondo giocatore.
<BR>
<BR>Ciao
<BR>Marino
<BR>
<BR>Edit: D\'oh!!!<BR><BR>[ Questo Messaggio è stato Modificato da: gip il 11-12-2004 18:48 ]

Avatar utente
gip
Messaggi: 86
Iscritto il: 01 gen 1970, 01:00
Località: Pisa, Scuola Superiore Sant'Anna
Contatta:

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.
<BR>
<BR>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).
<BR>
<BR>Ciao
<BR>Marino <IMG SRC="images/forum/icons/icon_wink.gif">

Avatar utente
jim
Messaggi: 125
Iscritto il: 01 gen 1970, 01:00
Località: Asti

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...
<BR>La tua nuova versione dell\'esercizio, invece, non ho la più pallida idea di come risolverla.
<BR>

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-12-11 19:02, gip wrote:
<BR>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).
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ok. Io ci sto. 2004 p.ti numerati da 1 a 2004. Comincio io. Congiungo 1 e 2.
<BR>
<BR>Ciao. M.[addsig]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

ReKaio
Messaggi: 565
Iscritto il: 01 gen 1970, 01:00
Località: Terra degli Shura (pisa)
Contatta:

Messaggio da ReKaio » 01 gen 1970, 01:33

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

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-12-14 09:38, ReKaio wrote:
<BR>uhm... dimostrazione per autorevolezza.. ha scelto di giocare per primo, quindi esiste una strategia vincente per chi inizia. cvd
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Lol!!
<BR>
<BR>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...
<BR><IMG SRC="images/forum/icons/icon_wink.gif">
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Bloccato