[C, N] : Insiemi e divisori.

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

Consideriamo l\'insieme di interi {1...2n}, ed un suo qualsiasi sottoinsieme S formato da almeno n+1 elementi. Dimostrare:
 a) esistono x, y in S tali che x | y
 b) esistono x, y in S primi tra loro.
 [ Questo Messaggio è stato Modificato da: Catraga il 18-10-2004 10:59 ]

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

a) Ogni numero naturale positivo può scriversi, e univocamente, nella forma 2r · q, ove r, q \\in N0 e q = 1 mod 2. E allora, in particolare, detti a1, a2, ..., an+1 gli n+1 elementi dell\'insieme {1, 2, ..., 2n} appartenenti ad S, con n \\in N0, si ha che, per ogni k = 1, 2, ..., n+1: ak = (2^rk) · qk, ove ancora rk, qk \\in N0 e qk è un dispari intero compreso fra 1 e 2n - 1. E poiché i dispari naturali compresi fra 1 e 2n-1 sono in numero pari ad n, ne consegue - per il principio dei cassetti - ch\'esistono i, j = 1, 2, ..., n+1, con i < j, tali che: qi = qj = q, di modo che: ai = 2i · q ed aj = 2j · q, e di conseguenza: ai | aj. Di qui l\'asserto.
 
 
 b) Di n + 1 interi a1, a2, ..., an+1 scelti ad arbitrio nell\'insieme {1, 2, ..., 2n}, ne esistono necessariamente almeno due consecutivi. Diversamente, infatti, supposto (come lecito): a1 < a2 < ... < an+1, si avrebbe a dedurre che: 2n >= an+1 >= 2 + an >= ... >= 2n + a1 >= 2n + 1, in evidente assurdo! Di qui la tesi, pur di considerare che il massimo comun divisore di due interi consecutivi è sempre uguale ad 1.
 
 
 \"Un uomo inizia a palesarsi per quello che è quando il suo talento comincia a scemare, quand\'egli smette di mostrare ciò che può. Il talento è pure un ornamento, e un ornamento è pure un nascondiglio.\" - F. W. Nietzsche, Così parlò Zaratustra [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 18-10-2004 14:25 ]

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

Mamma mia! Soluzione ineccepibile, ma brutale! Suvvia, si puo\' dimostrare in modo molto piu\' semplice e piu\' elegante (la bravura sta proprio qua...). Sono due esercizietti sul principio della piccionaia...
 
 
 \"La bravura di un matematico non si valuta col dimostrare con termini altisonanti e ragionamenti complessi, ma con l\'utilizzare il minimo di definizioni e la massima semplicita\' di pensiero \" - Catraga, parafrasando Hamilton.

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

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-10-18 18:31, Catraga wrote:
 
 Sono due esercizietti sul principio della piccionaia...
 
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 xchè euler cosa ha usato???!? <IMG SRC="images/forum/icons/icon_eek.gif">

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

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-10-18 18:31, Catraga wrote:
 \"La bravura di un matematico non si valuta col dimostrare con termini altisonanti e ragionamenti complessi, ma con l\'utilizzare il minimo di definizioni e la massima semplicita\' di pensiero \" - Catraga, parafrasando Hamilton.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Ché difatti IO non sono un Matematico, mio caro catraga! E\' sufficiente questo per giustificarmi? Ok, grassie... <IMG SRC="images/forum/icons/icon_confused.gif">
 
 P.S.: \"brutale\" in che senso, scusa? Penso di non aver mai esibito una soluzione così elementare in vita mia... <IMG SRC="images/forum/icons/icon_eek.gif">
 
 P.P.S.: psion, credi sia il caso ch\'io mi colleghi al sito web dell\'Accademia e mi scarichi il paper dei neologismi datati settembre 2004? No, sai perché te lo chiedo? Causa l\'estrema mia impùdica(1) insipienza, mi trovo a dover ricoscere che la parola \"xkè\" è del tutto estranea al mio vocabolario... <IMG SRC="images/forum/icons/icon_razz.gif">
 
 (1): ragioni metriche mi obbligano ad alterare la posizione naturale dell\'accento tonico! Il purista non si dispiccia... D\'altro canto, Dante stesso, parlando di Evaristo, lo citava come il gran \"geomètra\", sicché... <IMG SRC="images/forum/icons/icon_wink.gif">
 
 
 \"Questo tizio cerca rogne...\" - HiTLeuLeR parafrasando l\'omino del cervello

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

\"Brutale\" : questi esercizi possono essere risolti in modo molto rapido, senza impelagarsi in catene di disuguaglianze; le dimostrazioni sono corrette, ma a me paiono piu\' complesse del necessario... basta partizionare in modo astuto l\'isieme {1...2n} per creare delle corrette piccionaie (nel primo lo hai fatto - in modo molto arzigogolato, non c\'e\' che dire), il secondo:
 
 Lemma: gcd(k,k+1)=1 per ogni k intero.
 Partizioniamo {1...2n} negli insiemi {i,i+1} con i =1,3,5,7...2n-1.
 Abbiamo creato cosi\' 2n / 2 = n insiemi.
 Per il pigeonhole due elementi di S appartengono alla stessa partizione, indichiamoli con a[k1] ed a[k2], quindi {a[k1],a[k2]}={j,j+1} per qualche j.
 Per il lemma a[k1] ed a[k2] sono primi tra loro. Fatto.
 
 HiTLeuLeR, non ho mai insinuato, e mai mi e\' giunta idea dal mondo iperuranio, che tu fossi un matematico...
 <IMG SRC="images/forum/icons/icon_razz.gif">

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

Non sono d\'accordo con Catraga (e spero non me ne voglia per tale divergenza). La soluzione che ha postato HiTLeuLeR è la medesima presente in tutti i libri di problem-solving relativa a questo (classico) problema del semplice quanto stupendo Pigeonhole/Box Principle, ed è la più \"naturale\". Non mi pare assolutamente giustificabile il definirla brutale. E\' pur vero che alle volte il nostro misero ingeniere si affida a troppa retorica per risolvere i problemi, ma anche questa colpa non gli è imputabile: ognuno si esprime come vuole e non è un delitto rendere \"barocco\" un proof.
 
 P.S.: HiTLeuLeR, ti arriverà a casa la mia parcella...

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

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-10-19 08:34, Catraga wrote:
 HiTLeuLeR, non ho mai insinuato, e mai mi e\' giunta idea dal mondo iperuranio, che tu fossi un matematico... <IMG SRC="images/forum/icons/icon_razz.gif">
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Beh, se non alto... curioooso! Leggendo di quel che scrivi e delle obiezioni che mi muovi, sai che di te ho pensato anch\'io lo stesso? <IMG SRC="images/forum/icons/icon21.gif">
 
 
 \"Chi semina vento, raccoglie tempesta.\" - saggezza antica

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

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-10-19 10:45, DB85 wrote:
 E\' pur vero che alle volte il nostro misero ingeniere si affida a troppa retorica per risolvere i problemi, ma anche questa colpa non gli è imputabile: ognuno si esprime come vuole e non è un delitto rendere \"barocco\" un proof.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Quest\'è la parte che più mi piace, DB85! E se ti proponessi di essere la mia fidanzata piuttosto che il mio avvocato difensore? La parcella dovrei pagartela comunque? Uff... il tuo morboso attaccamento al vile denaro è proprio da ingegneri, sai? Vergognati!!! Ed io che ti stavo offrendo il mio amore, gh... <IMG SRC="images/forum/icons/icon_frown.gif">
 
 
 \"Questa è una ca...!!! Una grande c***a...!!! Una grossa, gigantesca, strepitosa c***ata!!!\" - la tv