OliForum Matematico

Problema 1: dimostrare che, per ogni m, n \\in N0 tali che n >= m,
 [gcd(m, n)/n] · Bin(n, m) è un numero intero, ove Bin(n, m) denota - come al solito - il coefficiente binomiale di ordine n su m.
 
 
 \"Chi si rilassa troppo finisce per cagarsi addosso.\" - HiTLeuLeR [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 12-10-2004 18:36 ]

Temo di non capire cosa sia gcd(m,n)

No problem, siamo qui per questo! Banalmente: gcd = greatest common divisor. Dannati inglesismi, vero? A buon rendering...
 
 
 \"Sedurre il prossimo a una buona opinione e poi credere con credulità a questa buona opinione: nessuno è più abile delle donne in questo pezzo di bravura.\" - F. W. Nietzsche, Al di là del bene e del male

ci son quasi.... \'pettate eh? <IMG SRC="images/forum/icons/icon_wink.gif"> [addsig]

Oh! Gaudeamus, igitur... <IMG SRC="images/forum/icons/icon_wink.gif">
 
 
 \"Potis est vis ulla tenere ingenium.\" - HiTLeuLeR parafrasando Virgilio

uff..... e\' da stamattina che non gli do\' un\'occhiata.... maledetto lavoro!! spero non me la portiate via... (la soluzione)
 <IMG SRC="images/forum/icons/icon_biggrin.gif"> [addsig]

uff.. finalmente! eppure a rivederlo adesso mi sembra una sciocchezza... cmq.
 
 Th.:
 
 (gcd(n, m)/n) * bin(n, m) = k con:
 
 n,m,k app. N e n >= m
 
 Dim.:
 
 Trascriviamo la formula del binomiale:
 
 
 bin(n, m) = n! / (m! * (n - m)!)
 
 se semplifichiamo n! con m! otteniamo la produttoria da n a (n - m + 1).
 
 Trascriviamo quindi la formula iniziale:
 
 (gcd(n, m) / n) * ( n(n - 1).....(n - m + 1) ) / (n - m)!)
 
 
 semplifichiamo ed eliminiamo la n dalle due frazioni.
 
 Nella seconda frazione, a numeratore abbiamo il prodotto di (n - m) numeri consecutivi e a denominatore abbiamo proprio (n - m)! (fattoriale) quindi il quoto e\' un numero naturale (va dimostrato pure questo? e\' banale...) che moltiplicato per gcd(n, m) da\' un altro numero naturale.
 
 c.v.d.
 
 mo\' mi merito sta birra!
 
 
 
 [ Questo Messaggio è stato Modificato da: darko il 22-10-2004 09:43 ]
 Mancava una parentesi [ Questo Messaggio è stato Modificato da: darko il 22-10-2004 09:58 ]

darko, ho visto il tuo proof velocemente ma mi sembra contenga molti mistakes!
 
 P.S.: Mi chiedo quando arriverà la sfuriata di HiTLeuLeR...

tipo ??

Tipo quando semplifichi n! per m!... Infatti: n*(n-1)*...*(m+1)*m! = n! e non n*(n-1)*...*(n-m+1)*m!. In questo modo ti esce l\'uguaglianza n*(n-1)*...*(n-m+1)/(n-m)! = n*(n-1)*...*(n-m+1)*/m!, valida solo per n = 2m. [ Questo Messaggio è stato Modificato da: DB85 il 22-10-2004 16:14 ]

neeeee.......<IMG SRC="images/forum/icons/icon_eek.gif">
 
 non e\' possibile... spe, spetta.... fammi ricontrollare per la decima volta.....
 
 
 <IMG SRC="images/forum/icons/icon_eek.gif">

ok, e\' vero ho cappellato quella cosa, diciamo la \"scrittura\", ma la sostanza non cambia. devo solo riscriverla per benino...
 
 come Wiles mi ritiro un attimo per pensare... <IMG SRC="images/forum/icons/icon_smile.gif">[addsig]

mah nel frattempo me ne vo a casa. mi tocchera\' aspettare lunedi\' per la conclusione che la telecom bastarda m\'ha staccato il telefono.
 
 
 byezzzzzzzzzzzz[addsig]

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-10-22 09:39, darko wrote:
 [...] mo\' mi merito sta birra!
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Sì, ceeerto! Te ne meriteresti una cassa intera... sulla testa, però!!!
 
 
 \"Ti consiglio d\'imbarcarti a bordo del primo treno bianco per Lourdes: chissà che non avvenga di nuovo il miracolo...\" - HiTLeuLeR

Simboli:
 
 a==b (m) a congruo b modulo m
 [m/n]= parte intera del rapporto m/n
 gcd(m,n)= (m,n) = d (in futuro la virgola sarà in carattere normale)
 Bin(m n) = (m n)
 
 Lemma 1
 
 m,n sono numeri naturali tali che m>n
 Allora
 (m,n) = m-[m/n]*n
 
 Dimostrazione:
 
 Consideriamo il seguente problema:
 Detrminare il numero di quadratini, Q, attraversati dalla diagonale di un rettangolo di n*m quadratini unitari.
 
 Soluzione 1
 
 se m==0 (n) allora Q=m
 
 altrimenti
 Q=([m/n]+1)*n il numero di quadratini attraversati dalla diagonale del rettangolo è uguale al numero di quadratini attraversati dalla diagonale del rettangolo omotetico a quello dato con rapporto di omotetia 1/n, moltiplicati per n.
 
 Soluzione 2
 
 se (m,n)=1 allora la diagonale non passa per nessun vertice di quadratini interni e dunque l\'attraversamento di ogni riga orizzontale di ogni riga verticale determinano il passaggio da un quadratino all\'altro, perciò:
 Q=1 (quadratino di partenza) +(m-1)+(n-1)=m+n-1
 
 se (m,n)=d allora la diagonale passa per d-1 vertici di quadratini interni al rettangolo perciò al numero precedente occorre togliere d-1:
 Q=m+n-d
 
 Confrontando le due soluzioni otteniamo la seguente identità:
 
 ([m/n]+1)*n=m+n-d
 da cui
 d= m-[m/n]*n come volevasi dimostrare.
 
 Dimostrato questo lemma torniamo al problema originale cercando di dimostrare la proposizione data partendo da una nota identità e manipolandola con passaggi corretti:
 
 (m n)= m/n *(m-1 n-1)
 
 (m,n)*(m n)= m/n *(m-1 n-1) * (m,n)
 
 (m,n)/m *(m n)= (m,n)/n *(m-1 n-1)
 
 sostituendo nel membro di destra dell\'uguaglianza il lemma 1 otteniamo:
 
 (m,n)/m *(m n)= ((m-[m/n]*n)/n)*(m-1 n-1)
 
 (m,n)/m *(m n)= m/n*(m-1 n-1) - [m/n]*(m-1 n-1)
 
 (m,n)/m *(m n)= (m n) - [m/n]*(m-1 n-1)
 
 Come volevasi dimostrare a sinistra abbiamo il termine richiesto dal problema e a sinistra un numero naturale perchè differenza di due naturali.
 Nice problem, bye. <IMG SRC="images/forum/icons/icon_wink.gif">

OliForum Matematico

[N] Binomiali e fattoriali.