combinazioni elementari

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
antonir91
Messaggi: 2
Iscritto il: 22 set 2009, 13:50

combinazioni elementari

Messaggio da antonir91 »

tratto dagli enigmi di canterbury, ernest dudeney
l'enigma del frate
[...] "se il frate bisognoso riceve come offerta 500 penny, vi prego di dirmi in quanti modi differenti egli può sistemarli in 4 sacchetti" il buon uomo spiegò che l'ordine nn faceva differenza (e dunque la distribuzione 50,100,150,200 sarebbe stata uguale a 100,50,200,150) e uno, due, o tre dei sacchetti potevano risultare vuoti in ogni momento
matty96
Messaggi: 343
Iscritto il: 21 apr 2010, 14:30
Località: Matelandia di Calabria (CS)

Messaggio da matty96 »

Se ho capito bene il frate può sistemare i 500 penny in qualunque modo nei quattro sacchetti,quindi bisogna calcolare le possibili combinazioni dei 500 penny nei 4 sacchetti:$ \binom {500}{4} $.Non è difficile fare il conto(anche se viene grosso).Basta che fai il conto delle disposizioni tra 500 e 4 e lo dividi per 4!.Svolti i conti dovrebbe uscire come risultato: 2.573.031.125.

Se non ho sbagliato i conti
<<Se avessi pensato (se pensassi) che la matematica è solo tecnica
e non anche cultura generale; solo calcolo e non anche filosofia,
cioè pensiero valido per tutti, non avrei fatto il matematico (non
continuerei a farlo)>> (Lucio Lombardo Radice, Istituzioni di
Algebra Astratta).
Mathforum
$ \displaystyle\zeta(s)=\sum_{n=1}^\infty \frac {1}{n^s} $
Avatar utente
Gatto
Messaggi: 487
Iscritto il: 25 nov 2007, 16:36
Località: Roma

Messaggio da Gatto »

@Matty: quando sei in dubbio con qualche formula, prova a sperimentarla in casi analoghi più semplici... se avessi 4 penny e 4 sacchetti, il numero di modi sarebbe $ \binom{4}{4} = 1 $? ;)
"Fu chiaro sin dall'inizio che ogni qual volta c'era un lavoro da fare, il gatto si rendeva irreperibile." (George Orwell - La fattoria degli animali)
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

non sono sicuro che quella formula sia giusta.
Quel binomiale ti dice quanti sottoinsiemi non ordinati di 4 elementi puoi avere

con 4 pennys hai 5 possibilita' (sacchetti vuoti sono accettati ;) ) o 1 senza sacchetti vuoti
con 5 pennys hai sempre 1 possibilita' senza sacchetti vuoti (6 coi sacchetti vuoti)
con 6 pennys 2 senza sacchetti vuoti
come vedi non torna col tuo conto
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
sasha™
Messaggi: 328
Iscritto il: 11 mag 2009, 12:58

Messaggio da sasha™ »

La partizione di 500 in 4, incluso lo zero, è $ \binom {500 + 4 - 1}{4 - 1} = \binom {503}{3} $, però è ordinata. E non si può nemmeno dividere per $ 4! $, perché bisogna considerare le ripetizioni.

Dunque, c'è un solo caso in cui un numero si ripete 4 volte, ossia 125 - 125 - 125 - 125.
I numeri che si possono ripetere 2 volte sono da 0 a 250, ovvero 251. Però in questo modo il contenuto dei restanti due sacchetti non è determinato. Se i primi due sacchetti contengono $ k $ penny, allora il numero di partizioni possibili negli altri due sacchetti è $ 500 - 2k $. I casi possibili con almeno due ripetizioni sono quindi la sommatoria per k da 0 a 250 di $ 500 - 2k $, che è uguale a $ 250*251 $, a meno dell'ordine.

In totale sono quindi $ [\binom {503}{3} - (250*251 - 1)]/4! + 250*251 $, svolgendo il calcolo
$ [503*502*501/6 - (250*251 - 1)]/24 + 250*251 $ =
= $ (503*251*167 - 250*251 + 1)/24 + 250*251 $ =
= $ [251*(503*167 + 250*23) + 1]/24 = 540660048 $

Ma mi sembra un po' troppo complicato, per un giochino apparentemente semplice.
matty96
Messaggi: 343
Iscritto il: 21 apr 2010, 14:30
Località: Matelandia di Calabria (CS)

Messaggio da matty96 »

Mamma mia che vergogna!!!!!!! :oops: Sono proprio uno sciocco.Scusatemi per la figuraccia.La prossima volta ci penserò un miliardo di volte prima di postare.Scusatemi ancora
<<Se avessi pensato (se pensassi) che la matematica è solo tecnica
e non anche cultura generale; solo calcolo e non anche filosofia,
cioè pensiero valido per tutti, non avrei fatto il matematico (non
continuerei a farlo)>> (Lucio Lombardo Radice, Istituzioni di
Algebra Astratta).
Mathforum
$ \displaystyle\zeta(s)=\sum_{n=1}^\infty \frac {1}{n^s} $
trugruo
Messaggi: 192
Iscritto il: 31 ago 2009, 15:04

Messaggio da trugruo »

matty96 ha scritto:Mamma mia che vergogna!!!!!!! :oops: Sono proprio uno sciocco.Scusatemi per la figuraccia.La prossima volta ci penserò un miliardo di volte prima di postare.Scusatemi ancora
Tranquillo,è proprio dagli errori che si impara,più si sbaglia più si impara,non devi vergognarti delle tue soluzioni,anche se sbagliate.Questo forum è fatto per imparare.
Avatar utente
io.gina93
Messaggi: 386
Iscritto il: 24 apr 2010, 01:29

Messaggio da io.gina93 »

matty96 ha scritto:Mamma mia che vergogna!!!!!!! :oops: Sono proprio uno sciocco.Scusatemi per la figuraccia.La prossima volta ci penserò un miliardo di volte prima di postare.Scusatemi ancora
tranquillo, pensa a come ho risolto io i problemi!! Così ti tiri sù di morale!! :D
sasha™
Messaggi: 328
Iscritto il: 11 mag 2009, 12:58

Messaggio da sasha™ »

Ma quello che ho scritto io è giusto oppure è una cazzata immane? :?
amatrix92
Messaggi: 818
Iscritto il: 21 nov 2008, 17:19
Località: Firenze

Messaggio da amatrix92 »

sasha™ ha scritto:Ma quello che ho scritto io è giusto oppure è una cazzata immane? :?
Io ho solo il risultato numerico e il tuo è sbagliato (anche come numero di cifre).
Le parole non colgono il significato segreto, tutto appare un po' diverso quando lo si esprime, un po' falsato, un po' sciocco, sì, e anche questo è bene e mi piace moltissimo, anche con questo sono perfettamente d'accordo, che ciò che è tesoro e saggezza d'un uomo suoni sempre un po' sciocco alle orecchie degli altri.
sasha™
Messaggi: 328
Iscritto il: 11 mag 2009, 12:58

Messaggio da sasha™ »

Allora riprovo.

Il fatto che le partizioni ordinate siano $ \binom {503}{3} $ è vero.

Ok, reset. Sto facendo confusione.

Suppongo di voler mettere lo stesso numero di monete in due sacchetti. Quel numero (che chiamo k) è compreso fra 0 e 250, e quindi lo posso scegliere in 251 modi.
Il terzo sacchetto può contenere fra 0 e 500 - 2k monete. Ma io voglio che, per evitare ripetizioni, ne contenga meno del quarto, o al massimo lo stesso numero. Quindi può contenerne al massimo 250 - k. Le possibilità complessive sono la sommatoria da 0 a k di 251 - k, ossia 126*251. Di questi, 166 sono i casi in cui si ripetono tre numeri, e 1 il caso in cui se ne ripetono 4. 250 sono i casi in cui ho due coppie, che ho contato due volte, e che devo quindi togliere.

125*251 + 1 casi possibili NON ORDINATI, con almeno due ripetizioni.
Nei 125*251 - 166 casi in cui vi sono solo due ripetizioni, devo moltiplicare per 12 per considerare l'ordine.
Nei 166 casi in cui vi sono tre ripetizioni, devo moltiplicare per 4.
Nell'unico caso in cui vi sono quattro ripetizioni, non devo moltiplicare.
Nei 250 casi nei quali vi sono due coppie, devo moltiplicare per 6, ma dividere per 2, visto che quei 250 sono tutti casi "doppi".

Calcoliamo. [503*251*167 - (125*251 - 166)*12 - 166*4 - 125*6 - 1]/24 + (125*251 - 166) + 166 + 125 + 1, dovrebbe essere la risposta. Che, a conti fatti, è 894348.

Ditemi che è giusta, ci ho perso un sacco di tempo e di correzioni. :shock:
amatrix92
Messaggi: 818
Iscritto il: 21 nov 2008, 17:19
Località: Firenze

Messaggio da amatrix92 »

sasha™ ha scritto:Allora riprovo.

Il fatto che le partizioni ordinate siano $ \binom {503}{3} $ è vero.

Ok, reset. Sto facendo confusione.

Suppongo di voler mettere lo stesso numero di monete in due sacchetti. Quel numero (che chiamo k) è compreso fra 0 e 250, e quindi lo posso scegliere in 251 modi.
Il terzo sacchetto può contenere fra 0 e 500 - 2k monete. Ma io voglio che, per evitare ripetizioni, ne contenga meno del quarto, o al massimo lo stesso numero. Quindi può contenerne al massimo 250 - k. Le possibilità complessive sono la sommatoria da 0 a k di 251 - k, ossia 126*251. Di questi, 166 sono i casi in cui si ripetono tre numeri, e 1 il caso in cui se ne ripetono 4. 250 sono i casi in cui ho due coppie, che ho contato due volte, e che devo quindi togliere.

125*251 + 1 casi possibili NON ORDINATI, con almeno due ripetizioni.
Nei 125*251 - 166 casi in cui vi sono solo due ripetizioni, devo moltiplicare per 12 per considerare l'ordine.
Nei 166 casi in cui vi sono tre ripetizioni, devo moltiplicare per 4.
Nell'unico caso in cui vi sono quattro ripetizioni, non devo moltiplicare.
Nei 250 casi nei quali vi sono due coppie, devo moltiplicare per 6, ma dividere per 2, visto che quei 250 sono tutti casi "doppi".

Calcoliamo. [503*251*167 - (125*251 - 166)*12 - 166*4 - 125*6 - 1]/24 + (125*251 - 166) + 166 + 125 + 1, dovrebbe essere la risposta. Che, a conti fatti, è 894348.

Ditemi che è giusta, ci ho perso un sacco di tempo e di correzioni. :shock:
notevole, sì la risposta è giusta!

BONUS:trovare una formula unica per $ n $ penny. La soluzione non mi sembra affatto banale.
Le parole non colgono il significato segreto, tutto appare un po' diverso quando lo si esprime, un po' falsato, un po' sciocco, sì, e anche questo è bene e mi piace moltissimo, anche con questo sono perfettamente d'accordo, che ciò che è tesoro e saggezza d'un uomo suoni sempre un po' sciocco alle orecchie degli altri.
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

amatrix92 ha scritto:BONUS:trovare una formula unica per $ n $ penny. La soluzione non mi sembra affatto banale.
Infatti, la parola giusta è "straightforward":

$ $\left\lfloor\frac{2n^3+30n^2+9(15+(-1)^n)n+319}{288}\right\rfloor $.

Contro-bonus: quanti sono i modi di ripartire le 500 monetine in mucchietti, ognuno dei quali non contenga più di 4 monetine? (nuovamente, l'ordine non fa differenza)
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
sasha™
Messaggi: 328
Iscritto il: 11 mag 2009, 12:58

Messaggio da sasha™ »

Tibor Gallai ha scritto:Contro-bonus: quanti sono i modi di ripartire le 500 monetine in mucchietti, ognuno dei quali non contenga più di 4 monetine? (nuovamente, l'ordine non fa differenza)
Mmh. Divido le monetine in 125 mucchietti da 4. Ogni mucchietto da 4 può restare com'è, o venire diviso come 1-1-1-1, 1-1-2, 1-3, 2-2. In totale può essere diviso in 5 modi diversi. Mi verrebbe da dire 625, ma mi sa che così non considero tutti i casi.
Infatti la combinazione 123 [4] + 2 [3] + 1 [2] è possibile, ma non è prevista dal mio calcolo.
Ragioniamoci un attimo: ci sono altri casi possibili non previsti dal mio calcolo? Provando a dividere un mucchietto di 8 monete secondo la regola, l'unico caso che non posso ottenere partendo da due mucchietti da 4 è proprio 3-3-2.
E se provassi a dividere un mucchietto da 12? La soluzione 3-3-3-3, ad esempio, non sarebbe possibile né con tre mucchietti da 4, né con uno da 8 e uno da 4. E anche questa volta è l'unica.
Passando a 16, tutte le combinazioni invece possono essere ottenute partendo da un mucchietto da 12 e uno da 4. Stessa cosa da 20 in su.

Il mucchietto da 12 è quello che mi dà tutte le possibilità, essendo 12 mcm (2, 3, 4). Solo che 500 non è divisibile per 12: posso formare allora 41 mucchietti da 12 e uno da 8.
Per dividere i primi, ho 5+5+5+1+1 = 17 possibilità. Per il secondo, 5+5+1 = 11.

A questo punto dovrebbe bastare fare 41*17 + 11 = 708. È giusto?
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Rofl. Sono un po' di più. Inoltre, la mia domanda non è posta a caso (vado controtendenza, lo so).
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
Rispondi