-
lumo.
User deleted
Un esercizio interessante: www.codechef.com/problems/MARBLES
In pratica, avendo k colori, e infinite biglie di ogni colore, voglio prendere n biglie, ma tra queste n ne devo avere almeno una per ogni colore. Calcolare in quanti modi posso fare ciò.
La parte algoritmica non è fondamentale quindi ho messo l'esercizio nella sezione di matematica
. -
~Andrey™.
User deleted
Uhm... diciamo che secondo le ipotesi almeno k biglie deve averle di colori diversi, quindi non c'è alcuna 'scelta' fin qui. Le restanti n - k biglie può prenderle di qualunque colore, anche con ripetizioni, quindi direi che per ognuna delle n-k biglie rimaste può scegliere tra k colori.
In definitiva l'insieme delle scelte che può fare ha dimensione k^(n-k).
Ci sono?
. -
lumo.
User deleted
Uhm... diciamo che secondo le ipotesi almeno k biglie deve averle di colori diversi, quindi non c'è alcuna 'scelta' fin qui. Le restanti n - k biglie può prenderle di qualunque colore, anche con ripetizioni, quindi direi che per ognuna delle n-k biglie rimaste può scegliere tra k colori.
In definitiva l'insieme delle scelte che può fare ha dimensione k^(n-k).
Ci sono?
Shit, sarebbe giusto però mi sono dimenticato di dire che non conta l'ordine in cui vengono prese asdasd.
. -
lumo.
User deleted
Su nessuno prova? 
Se volete do qualche hint.. -
~Andrey™.
User deleted
Ah se non conta l'ordine si tratta di combinazioni con ripetizioni, ora però non posso proprio farlo... Appena posso mi ci metto 
. -
CaMpIoN.
User deleted
Considerando n>=k allora ci saranno sicuramente biglie con lo stesso colore, in questo caso io ragionerei in questo modo:
Dato che tra le n biglie devo averne almeno una di ogni colore avrò k biglie di colore diverso mentre le restanti saranno di qualsiasi colore, quindi k biglie rimarranno fisse mentre le n-k varieranno e in precisione, dato che non conta l'ordine, varieranno in base alle combinazioni con ripetizione di k elementi di classe n-k, ovvero.
In realtà per avere tale risultato devi considerare come diversità di ogni combinazione la diversità del colore delle biglie. Se infatti come diversità scegliessi ogni biglia, anche dello stesso colore, allora avrei infinite combinazioni possibili essendo infinite le biglie.
Nel caso n<k allora non posso mai ottenere una combinazioni con tutti e k i colori.
Provando per esempio con 2 colori, rosso e blu, e 3 biglie, per la formula dovrei avere:
In effetti se fisso le due biglie dovrò prendere una sola biglia, quindi o la rossa o la blu, cioè due combinazioni:
rosso,blu, rosso
rosso,blu,blu
La formula sembra funzionare.
Edited by CaMpIoN - 28/4/2014, 10:08.
Marbles |
