Salve, vi propongo un problema trovato in un allenamento online a squadre (simulazione di gara in preparazione per Cesenatico) riguardante unicamente il calcolo combinatorio, purtroppo non sono riuscito a trovare le soluzioni online per confrontarle con quanto ho trovato, quindi ve lo sottopongo in modo da riuscire a capire se la mia soluzione (e il mio percorso per raggiungerla) sono giusti.
Il problema è il seguente:
Abbiamo a disposizione 3 tipi di dischi, dischi gialli (spessore di 6 cm), rossi (spessore di 10 cm) e verdi (spessore di 15 cm). Per ciascun tipo ne abbiamo tantissimi. Vogliamo costruire una colonna alta esattamente 90 cm impilando alcuni dischi, ma facendo in modo che i dischi gialli utilizzati siano di più sia dei rossi che dei verdi. Quante diverse colonne posso costruire? (Si considerino uguali due colonne se, partendo dalle base e salendo, la sequenza di dischi è la stessa).
Ci sono dischi gialli G=6, dischi rossi R=10 e dischi verdi V=15. Per il fatto che i gialli devono essere più dei verdi e dei rossi, ce n'è almeno uno.
Ora per ogni R o V che inserisco, devo inserire anche un G, altrimenti non soddisferei la condizione che i G siano maggiori in numero sia dei R che dei V, quindi posso completare la pila di $ 90-6=84\; $con i seguenti tre elementi:
-$ G=6 $, un disco giallo
-$ A=6+10=16 $, un disco rosso + un disco giallo
-$ B=6+15=21 $, un disco verde + un disco giallo
Quindi il problema diventa determinare tutte le terne $ \alpha , \beta , \gamma $ tali che $ \alpha A + \beta B + \gamma G = 84 $ e contarne le permutazioni dell'ordine con cui posso inserire i
dischi, che saranno in ogni caso $ \displaystyle \frac{(n_G+n_R+n_V)!}{(n_G)!(n_R)!(n_V)!} $ dove $ n_G $ indica il numero dei dischi gialli etc...
Per prima cosa noto che $ A $ non divide $ 84 $, quindi è una quantità che posso controllare facilmente. Per il teorema di Bezout $ \;MCD(G,B)=3\; $ deve dividere $ 84-\alpha A $. Da questa relazione ottengo che $ \alpha $ può essere solo 0 o 3. Analizzo prima il caso in cui $ \alpha = 0 $
$ 84=6\,\gamma + 21\,\beta $
$ 28=2\,\gamma + 7\,\beta $ da cui ottengo $ (\gamma,\beta)=\;(14,0)\;,\;(7,2)\;,\;(0,4) $: omettendo i calcoli abbiamo $ 1+66+126=193 $ permutazioni.
se $ \alpha=3 $
$ 84-3A=84-48=36=6\,\gamma+21\,\beta $
$ 12=2\,\gamma+7\,\beta $ da cui ottengo $ (\gamma,\beta)=\;(6,0)\; $: sempre omettendo i calcoli sono $ 286 $ permutazioni, che sommate alle $ 193 $ precedenti ci danno un totale di $ 479 $ combinazioni diverse
Credo ti manchino le permutazioni con 5 dischi gialli, 2 verdi e 3 rossi, che usando la formula che tu stesso hai citato sono $ \frac{{(5+2+3)! }}{5!+2!+3!}=2520 $ per un totale di 2999.. O almeno credo
Ultima modifica di AkaTux il 15 giu 2012, 09:17, modificato 1 volta in totale.
Proviamo quindi a risolvere $ 6x+10y+15z=90 $ quindi $ 2(3x+5y)=15(6-z) $, da cui $ 2|6-z $, poiché $ 6>z>0 $ in quanto si tratta di quantità nonnegative, si ha soltanto $ z=2,4 $.
1) Se $ z=2 $, si ha $ 3x+5y=30 $, quindi $ 3x=5(6-y) $ da cui $ 3|6-y $, per lo stesso ragionamento di $ z $ si ha $ y=3 $ che genera la soluzione $ x=5 $.
Abbiamo la terna $ (x,y,z)=(5,3,2) $.
2) Se $ z=4 $, si ha $ 3x+5y=15 $ che è evidentemente impossibile con $ (x,y)\in \mathbb{N}^2 $, volendo
la strada per dimostrare che è impossibile è la stessa del punto 1.
Quindi esiste solo una terna che mi permette di costruire la torre.
Le permutazioni di tutti i dischi è data da: $ P=\dfrac{10!}{5!3!2!}=2520 $.
Ultima modifica di Hawk il 14 giu 2012, 23:36, modificato 1 volta in totale.
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »
Non ho ben capito tutto ciò che hai scritto Hawk, ma leggendo questo:
Quindi esiste solo una terna che mi permette di costruire la torre.
Mi pare di capire che tu poni il problema come se ci fosse solo una terna.. ma dimentichi la possibilità che vengano usati i dischi di soli due colori..
Inoltre non riesco a capire da dove provenga la formula che usi alla fine $ P=\dfrac{10!}{5!+3!+2!}=28350 $ dato che per quanto ne so io per calcolare le varie combinazioni possibili con più elementi ripetuti dovrebbe essere $ P=\dfrac{10!}{5!3!2!} $ come già diceva Ertool
Ahi, che grave errore che ho combinato. Edito immediatamente. Comunque non si suppone che la colonna sia composta da tutti e 3 i tipi di dischi?
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »
Comunque sostituendo $ A=R+G=16 $ con $ R=10 $ e fissando la quantità degli $ R $, applicando lo stesso procedimento ottengo che $ 84-10\;\alpha $ deve essere multiplo di $ 3 $ e alla fine trovo anche la soluzione $ (\alpha , \beta , \gamma)=(3,2,2) $ che mi conduce alla terna $ (n_G,n_R,n_V)=(5,3,2) $, ovvero quella che perdevo inserendo $ A $ invece di $ R $.
