Luca e i suoi strani amici
Luca e i suoi strani amici
Luca ha n amici. Quando esce con loro, ognuno di essi gli dà un euro. Se Luca esce con ogni possibile sottoinsieme di n, quanti euro avrà guadagnato alla fine?
Ultima modifica di balossino il 04 ott 2011, 21:40, modificato 1 volta in totale.
Re: Luca e i suoi strani amici
Luca può uscire con un insieme di 1,2,3...n amici.
Quindi distinguiamo i casi...
-quando esce con 1 persona lo può fare in $n$ modi, quindi sono $n$ euro
-quando esce con 2 persone lo può fare in $\binom{n}{2}$ modi, ma ognuno di questi modi va moltiplicato per 2, dato che riceve 2 euro...
-questo ragionamento si applica per ogni $\binom{n}{k}$ con $k\leq n$, quindi il risultato è:
$\displaystyle \sum_{K=1}^{n} k \binom{n}{k}$
Quindi distinguiamo i casi...
-quando esce con 1 persona lo può fare in $n$ modi, quindi sono $n$ euro
-quando esce con 2 persone lo può fare in $\binom{n}{2}$ modi, ma ognuno di questi modi va moltiplicato per 2, dato che riceve 2 euro...
-questo ragionamento si applica per ogni $\binom{n}{k}$ con $k\leq n$, quindi il risultato è:
$\displaystyle \sum_{K=1}^{n} k \binom{n}{k}$
I tuoi problemi te li puoi anche tenere: a me, invece, non dispiacerebbe avere un camper come questo !
Re: Luca e i suoi strani amici
E il tuo risultato diventa...
Testo nascosto:
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: Luca e i suoi strani amici
Non ho capito il ragionamento di Drago perché sono arrivato alla soluzione attraverso un'altra strada... Comunque confermo che la formula è giusta, ma c'è un modo più stringato di scriverla
Re: Luca e i suoi strani amici
Provo a trovare una formula chiusa per la somma:
$ \displaystyle \sum_{k=0}^{n} k \binom{n}{k}=\displaystyle \sum_{k=0}^{n} k\cdot\binom{n-1}{k-1}+\displaystyle \sum_{k=0}^{n-1}k\cdot\binom{n-1}{k} $
Adesso sviluppiamo a parte le due somme:
$ \displaystyle \sum_{k=0}^{n} k\cdot\binom{n-1}{k-1}=\sum_{k=0}^{n-1}(k+1)\binom{n-1}{k}=\sum_{k=0}^{n-1}k\binom{n-1}{k}+ \sum_{k=0}^{n-1}\binom{n-1}{k}= $
$ \displaystyle\sum_{k=0}^{n-1}k\binom{n-1}{k}+ 2^{n-1}=\sum_{k=0}^{n-1}(n-1)\binom{n-2}{k-1}+ 2^{n-1}=n2^{n-2}-2^{n-2}+2^{n-1}=(n+1)2^{n-2} $
Sviluppiamo adesso l'altra formula:
$ \displaystyle \sum_{k=0}^{n-1} k\cdot\binom{n-1}{k}=\sum_{k=0}^{n-1}(n-1)\binom{n-2}{k-1}=n2^{n-2}-2^{n-2} $
Adesso sommiamo i due risultati ed otteniamo:
$ (n+1)2^{n-2}+(n-1)2^{n-2}=n2^{n-1} $
Un ringraziamento ad enigma!
$ \displaystyle \sum_{k=0}^{n} k \binom{n}{k}=\displaystyle \sum_{k=0}^{n} k\cdot\binom{n-1}{k-1}+\displaystyle \sum_{k=0}^{n-1}k\cdot\binom{n-1}{k} $
Adesso sviluppiamo a parte le due somme:
$ \displaystyle \sum_{k=0}^{n} k\cdot\binom{n-1}{k-1}=\sum_{k=0}^{n-1}(k+1)\binom{n-1}{k}=\sum_{k=0}^{n-1}k\binom{n-1}{k}+ \sum_{k=0}^{n-1}\binom{n-1}{k}= $
$ \displaystyle\sum_{k=0}^{n-1}k\binom{n-1}{k}+ 2^{n-1}=\sum_{k=0}^{n-1}(n-1)\binom{n-2}{k-1}+ 2^{n-1}=n2^{n-2}-2^{n-2}+2^{n-1}=(n+1)2^{n-2} $
Sviluppiamo adesso l'altra formula:
$ \displaystyle \sum_{k=0}^{n-1} k\cdot\binom{n-1}{k}=\sum_{k=0}^{n-1}(n-1)\binom{n-2}{k-1}=n2^{n-2}-2^{n-2} $
Adesso sommiamo i due risultati ed otteniamo:
$ (n+1)2^{n-2}+(n-1)2^{n-2}=n2^{n-1} $
Un ringraziamento ad enigma!
« 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. »
Re: Luca e i suoi strani amici
Io avrei usato $\displaystyle{\binom n k=\frac n k\binom{n-1}{k-1}}$ e $\displaystyle{\sum_{i=0}^n\binom n i=2^n}$ ed in un paio di passaggi arrivavo alla tua soluzione...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: Luca e i suoi strani amici
Oppure, in quanti sottoinsiemi compare un certo amico? $2^{n-1}$, quindi il numero è proprio $n2^{n-1}$!
Re: Luca e i suoi strani amici
Però è anche ben che impariate ad usare le interpretazioni combinatorie: se da un lato con questo procedimento è solo questione di qualche conto e si è sicuri di arrivare in fondo, l'altro metodo è più elegante e si risparmia spazio.
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: Luca e i suoi strani amici
Fico è geniale quell'approccio E chi ci avrebbe pensato? xD
Re: Luca e i suoi strani amici
Sarebbe molto bello... se riuscissi a capire perchè...Sonner ha scritto:Oppure, in quanti sottoinsiemi compare un certo amico? $2^{n-1}$
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: Luca e i suoi strani amici
Se tu assumi che un certo amico compare, gli altri n-1 amici possono o comparire o non comparire, quindi per ognuno dei rimanenti ci sono 2 possibilità.
Re: Luca e i suoi strani amici
Wow, geniale!xXStephXx ha scritto:Se tu assumi che un certo amico compare, gli altri n-1 amici possono o comparire o non comparire, quindi per ognuno dei rimanenti ci sono 2 possibilità.
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: Luca e i suoi strani amici
senza formule varie, usando solo il fatto che $\binom{n}{k}=\binom{n}{n-k}$.
arrivati alla somma $\sum^{n}_{i=0}i{\binom{n}{i}}$ e sfruttando il fatto sopra, vediamo che quella somma è uguale a $\frac{n}{2}\sum^n_{i=0}{\binom{n}{i}}+\frac{n}{2}$, e questa è uguale a $\frac{n(2^n-1)}{2}+\frac{n}{2}=n2^{n-1}$
arrivati alla somma $\sum^{n}_{i=0}i{\binom{n}{i}}$ e sfruttando il fatto sopra, vediamo che quella somma è uguale a $\frac{n}{2}\sum^n_{i=0}{\binom{n}{i}}+\frac{n}{2}$, e questa è uguale a $\frac{n(2^n-1)}{2}+\frac{n}{2}=n2^{n-1}$
"Mangiano solo mele, L, lo sai che gli shinigami, hanno le mani rosse?"
- Nonno Bassotto
- Site Admin
- Messaggi: 970
- Iscritto il: 14 mag 2006, 17:51
- Località: Paris
- Contatta:
Re: Luca e i suoi strani amici
Per chi conosce le derivate può essere anche carino osservare che
$ (1 + x)^n = \sum_{i = 0}^{n} \binom{n}{i}x^i $
e dunque, derivando,
$ n \cdot (1 + x)^{n - 1} = \sum_{i = 1}^{n} \binom{n}{i} \cdot i x^{i -1}. $
Per $ x = 1 $ si ottiene proprio $ n \cdot 2^{n - 1} = \sum_{i = 0}^{n} \binom{n}{i} \cdot i. $
$ (1 + x)^n = \sum_{i = 0}^{n} \binom{n}{i}x^i $
e dunque, derivando,
$ n \cdot (1 + x)^{n - 1} = \sum_{i = 1}^{n} \binom{n}{i} \cdot i x^{i -1}. $
Per $ x = 1 $ si ottiene proprio $ n \cdot 2^{n - 1} = \sum_{i = 0}^{n} \binom{n}{i} \cdot i. $
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill
Re: Luca e i suoi strani amici
ne approfitto per uppare un poco questo... Il secondo è una generalizzazione della sommatoria che si è dovuta risolvere in questo problema
Tanto per non farlo cadere nel dimenticatoio, visto che qualcuno mi aveva promesso una soluzione con le funzioni generatrici XD
Tanto per non farlo cadere nel dimenticatoio, visto che qualcuno mi aveva promesso una soluzione con le funzioni generatrici XD
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2
"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
1Cor 13:2
"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102