OliForum Matematico

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

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

@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 $?

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

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.

Mamma mia che vergogna!!!!!!! Sono proprio uno sciocco.Scusatemi per la figuraccia.La prossima volta ci penserò un miliardo di volte prima di postare.Scusatemi ancora

matty96 ha scritto:Mamma mia che vergogna!!!!!!! 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.

matty96 ha scritto:Mamma mia che vergogna!!!!!!! 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!!

Ma quello che ho scritto io è giusto oppure è una cazzata immane?

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).

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.

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.

notevole, sì la risposta è giusta!

BONUS:trovare una formula unica per $ n $ penny. La soluzione non mi sembra affatto banale.

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)

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?

Rofl. Sono un po' di più. Inoltre, la mia domanda non è posta a caso (vado controtendenza, lo so).