Soluzione all'enigma 44, proposto da Paolo P. il 23 maggio 2005

Il piccolo Pinuccio (amico di Gigetto, vedi enigma 26) è anche lui un bambino molto creativo e gioca con 11 contenitori di colori diversi che la mamma gli ha regalato. Ad un certo punto gli viene fame, va in cucina e trova in un barattolo la bellezza di 27 biscotti! Pinuccio è un golosone ed è molto contento della scoperta, ma essendo anche un bambino accorto, ne mangia solo 4 e vuole mettere i restanti 23 nei contenitori, e conservarli per i giorni successivi. Si accorge poi, che in ogni contenitore ci stanno al massimo 4 biscotti.  Allora Pinuccio si chiede: in quanti modi posso disporre i 23 biscotti negli 11 diversi contenitori con il vincolo di non poter mettere più di 4 biscotti per contenitore? Attenzione:
* I contenitori sono diversi, perché hanno diversi colori, per esempio: 2 in quello rosso e 1 in quello verde e diverso da 2 in verde e 1 in rosso o (2,1) non è uguale a (1,2)
* In ogni contenitore non necessariamente ci devo mettere un biscotto, non ho posto questo vincolo, se il problema lo consente alcuni possono rimanere anche vuoti.

La risposta corretta e` 4,004,770 modi,

*****

Paolo P. ci consente di iportare qui il modo in cui le persone hanno risolto il problema. E` un aspetto che lo affascina sempre,dice, a volte piu` della risposta in se.

Fulvia ha realizzato che il numero di possibilita` e` equivalente ad un numero in base 5 di 11 cifre la cui somma sia 23. Quindi basta contarli scrivendo un pogrammino. Le possibilita` da sondare sono 5^11.
Buono, ma quando i numero diventano grandi il sistema richiede troppo tempo.

Michela, ha scritto tutte le possibilita e ha calcolato quante volte si ripentono. es 4 4 4 4 4 3 0 0 0 0 si ripete 11!/5!4! volte, e poi sommando tutte le varie possibilita`.
Buono anche questo, ma poco verstile se cambio i numeri.

Stefano infine ha risolto il problema nel modo sotto riportato, e` ricorso all'utilizzo del computer ma sapete bene che io non sono contraio a queste cose. Il programmino non e` allegato.

************

SOLUZIONE propsta da Stefano

Indichiamo con f(m,n) il numero di modi di disporre m biscotti in n scatole, con un massimo di 4 biscotti per scatola. Fissiamo ora una scatola, diciamo la prima.   Questa puo' contenere 0,1,2,3 o 4 biscotti.
0 biscotti) Tutti gli m biscotti sono contenuti nelle rimanenti n-1 scatole.
1 biscotto) Restano m-1 biscotti disposti nelle n-1 scatole rimanenti.
2 biscotti) Restano m-2 biscotti disposti nelle n-1 scatole rimanenti
e analogamente gli altri. Ora il numero di disposizioni di m biscotti in n scatole sara' la somma di tutti i modi possibili di disporre i biscotti rimanenti nei 5 casi qui sopra, ovvero:
1) O biscotti nella prima: tutti i modi di disporre m biscotti in n-1 scatole, quindi f(m,n-1).
2) 1 biscotto nella prima: tutti i modi di disporre m-1 biscotti in n-1 scatole, quindi f(m-1,n-1)
e cosi' via. Morale:
f(m,n) = f(m,n-1) + f(m-1,n-1) + f(m-2,n-1) + f(m-3,n-1) + f(m-4,n-1)
Infine con un programmino si ottiene
f(23,11) = 4004770.