sns 2004/2005 #6

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
bruno222
Messaggi: 14
Iscritto il: 15 lug 2007, 13:56

sns 2004/2005 #6

Messaggio da bruno222 » 27 lug 2007, 13:12

Una partizione di un numero intero $ \n\ge 1 $ è una decomposizione di n in addendi interi (parti) $ m_1,.....m_k $ tali che $ m_i\ge 1 $ e $ m_1+.....+m_k=n $.
Per esempio le partizioni di 3 sono 3,2+1,1+1+1 e quelle di 4 sono 4,3+1,2+2,2+1+1,1+1+1+1.
Si dimostri che il numero delle partizioni di un intero n in al più r parti è uguale al numero delle sue partizioni in perti ciascuna al massimo uguale a r.



Buon lavoro!!

Avatar utente
pi_greco_quadro
Messaggi: 158
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Messaggio da pi_greco_quadro » 28 lug 2007, 17:58

Un bellissimo problema a mio parere! solamente che avendo pensato la soluzione sarei propenso a classificarlo come combinatoria...

Dunque le idee fondamentali sono queste

Diciamo che io voglia partizionare un $ n $ in al più $ k $ parti. Allora nessuno mi vieta di disegnare la mia partizione così come segue:

definisco una successione di righe $ r_0,r_1,\cdots, r_k $, ed in ognuna di queste coloro tante caselle quanto vale il valore dell'addendo che io desidero rappresentare in quella data riga. Chiaramente colorerò sempre un numero $ x\leq n $ di caselle e non è detto che sia obbligato ad utilizzare tutte le righe da me definite. Non importa: possiamo sempre pensare di associare ad una riga lasciata vuota l'addendo $ 0 $, assolutamente ininfluente nell'economia delle partizioni di un numero, e quindi del nostro problema.

Per spiegarmi, esemplifico con la partizione 4=3+1 e k=2

r_1= * * *
r_2= *

Ora, qui sta il giochino fighissimo di questo problema: per ogni partizione che abbiamo disegnato come sopra spiegato, supponiamo di ruotare il disegno corrispondente di $ 90° $ adottando come verso di rotazione quello antiorario. Bene, ci accorgiamo allora che tutte le righe sono diventate colonne e viceversa. Quindi ora avremo $ n $ righe ed al più $ k $ colonne, quindi potremmo disegnare solo addendi che valgono al più $ k $. Ora, per come noi abbiamo definito questa nostra applicazione, possiamo affermare che ad ogni disegno di partenza corrisponde uno ed uno solo disegno ruotato, ma quindi siamo in presenza di un'applicazione bigettiva, e questo conclude la dimostrazione del problema.
Disco es cultura, metal es religion (Metal py)
"Ti credevo uno stortone.. e pure vecchio.. (Lei)"

CoNVeRGe.
Messaggi: 98
Iscritto il: 22 ott 2008, 18:51

Messaggio da CoNVeRGe. » 07 ago 2009, 12:00

Up! :o

Come si può fare questo problema oltre al modo qui sopra (che non ho neanche capito) ?

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 07 ago 2009, 12:22

un disegnino vale più di mille parole (come dice il mio relatore triennale)

Codice: Seleziona tutto

*****        ****
***          **
*      --->  **
*            *
             *

Rispondi