Una gita a Primolandia.

[Sylvester]

Nello stato di Primolandia vi sono n città numerate con gli interi da 1 a n. Due città a e b sono collegate solo se a+b è un numero primo. Provare che esiste sempre una strada da una città all\'altra. (Dove per strada si intende un\'opportuna spezzata di collegamenti).[addsig]

[Azarus]

pensandoci sopra pochissimo tempo credo che sia una conseguenza del teorema di cebisev

[Sylvester]

Direi che hai pensato bene.

[Azarus]

dove hai trovato questo problema?

[Sylvester]

L\'ho inventato io.
<BR>
<BR>Comunque già che ci siamo riporto la soluzione completa. Procediamo per induzione.
<BR>
<BR>Per n=2 otteniamo {1,2}; 1+2=3 quindi siamo a posto. Supponiamo che l\'asserto valga per n-1 e proviamo che vale per n. Per il Teorema Di Tchebishev esiste sempre un primo p tale che n<p<2n, ovvero tale che p=n+x con x<n per cui x appartiene ad A, ma siccome per ipotesi di induzione esiste in A un\'opportuna \"strada\" da x ad ogni altro elemento di A, allora esiste anche una \"strada\" da n ad ogni elemento di A. q.e.d.
<BR>
<BR>
<BR>
<BR><font size=1>[ Questo Messaggio è stato Modificato da: Sylvester il 2002-06-09 12:43 ]</font>
<BR>
<BR><font size=1>[ Questo Messaggio è stato Modificato da: Sylvester il 2002-06-09 12:44 ]</font>
<BR>
<BR><font size=1>[ Questo Messaggio è stato Modificato da: Sylvester il 2002-06-09 12:45 ]</font><BR><BR><font size=1>[ Questo Messaggio è stato Modificato da: Sylvester il 2002-06-09 12:45 ]</font>

[Azarus]

davvero molto bello cmq
<BR>
<BR>a proposito...non ho scritto la soluzione per induzione perche non avevo voglia.... <IMG SRC="images/splatt_forum/icons/icon_razz.gif"> <IMG SRC="images/splatt_forum/icons/icon21.gif">

[BlaisorBlade]

C\'avevo pensato qualche tempo fa, e per induzione, dicevo: basta che se aggiungo la città n+1, n+1+x con 1<=x<=n sia primo, così la città n+1 ha una connessione e può raggiungere le altre. Base induttiva con 1 città, si continua con la verifica di ogni caso fino a 3, poi n+1+x può essere 5 con n<5, 7 con n<7, poi 13, 23(ogni elemento è il massimo possibile).(segue)<BR><BR><font size=1>[ Questo Messaggio è stato Modificato da: BlaisorBlade il 2002-06-08 19:41 ]</font>

[BlaisorBlade]

(segue dal messaggio prec.) Perché possa farlo sempre, basta che per ogni primo p della successione (5,7,ecc.) esista a primo con p minore di a minore di 2p. Mi sono bloccato qua. Ora il nocciolo: che cos\'è questo teorema di Tchebishev? Per caso il suo enunciato è proprio questo? È questa la vostra dimostrazione? Ricordatevi che esistono mortali che non conoscono questo teorema!
<BR>A proposito : ho notato che il mio messaggio veniva tagliato dove c\'era il simbolo di minore! Penso sia così anche per i vostri(e trattandosi di HTML non è difficile capire perché).<BR><BR><font size=1>[ Questo Messaggio è stato Modificato da: BlaisorBlade il 2002-06-08 19:44 ]</font>

[Sylvester]

Il teorema di Tchebishev afferma proprio che esiste sempre un numero primo tra n e 2n.
<BR>[addsig]

[BlaisorBlade]

Dimostrazione del teorema di Tchebishev?
<BR>E poi: i messaggi che hai mandato, correggili(se clicchi modifica appare il testo completo): elimina i simboli di maggiore e minore!(Non so perché, ma il primo messaggio mio è riuscito a mostrarlo; comunque tu prova, perché li taglia in quel punto preciso)

[Azarus]

la dim è un casino BB.
<BR>
<BR>Erdos lo dimostrò ma è sempre difficile<BR><BR><font size=1>[ Questo Messaggio è stato Modificato da: Azarus il 2002-06-09 12:34 ]</font>

[DD]

Basta mettere uno spazio prima e dopo i simboli < e > (o forse basta anche solo prima, o solo dopo).
<BR>

[DD]

La dimostrazione data da Erdos (quella di Chebyshev è incomprensibile) è <!-- BBCode Start --><A HREF="http://mathforum.org/library/drmath/view/51527.html" TARGET="_blank">qui</A><!-- BBCode End -->. Non è proprio di due righe ma è quasi leggibile.

[Azarus]

interessante...

[Antimateria]

Per ovviare a quei simpatici problemi di visualizzazione, basta modificare i messaggi e disattivare HTML e/o BBCode.
<BR>Enjoy!