Luca e i suoi strani amici

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
balossino
Messaggi: 103
Iscritto il: 20 mag 2011, 19:38

Luca e i suoi strani amici

Messaggio da balossino »

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.
Avatar utente
ale.G
Messaggi: 66
Iscritto il: 22 nov 2010, 15:14
Località: Lunghezza

Re: Luca e i suoi strani amici

Messaggio da ale.G »

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}$
I tuoi problemi te li puoi anche tenere: a me, invece, non dispiacerebbe avere un camper come questo !
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Luca e i suoi strani amici

Messaggio da Drago96 »

E il tuo risultato diventa...
Testo nascosto:
E se svolgessimo il binomiale, ricordandoci che è solo un prodotto con k al denominatore e che $(n+1)!=n!(n+1)$ ... :)
Magari arriviamo ad una formula che conosciamo...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Avatar utente
balossino
Messaggi: 103
Iscritto il: 20 mag 2011, 19:38

Re: Luca e i suoi strani amici

Messaggio da balossino »

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 :)
Hawk
Messaggi: 306
Iscritto il: 20 mag 2010, 19:16
Località: Roma

Re: Luca e i suoi strani amici

Messaggio da Hawk »

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! :D
« 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. »
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Luca e i suoi strani amici

Messaggio da Drago96 »

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)
Sonner
Messaggi: 364
Iscritto il: 12 feb 2009, 16:02
Località: Susa (TO)

Re: Luca e i suoi strani amici

Messaggio da Sonner »

Oppure, in quanti sottoinsiemi compare un certo amico? $2^{n-1}$, quindi il numero è proprio $n2^{n-1}$!
Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: Luca e i suoi strani amici

Messaggio da <enigma> »

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. :wink:
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: Luca e i suoi strani amici

Messaggio da xXStephXx »

Fico è geniale quell'approccio :mrgreen: E chi ci avrebbe pensato? xD
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Luca e i suoi strani amici

Messaggio da Drago96 »

Sonner ha scritto:Oppure, in quanti sottoinsiemi compare un certo amico? $2^{n-1}$
Sarebbe molto bello... se riuscissi a capire perchè... :cry:
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: Luca e i suoi strani amici

Messaggio da xXStephXx »

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à.
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Luca e i suoi strani amici

Messaggio da Drago96 »

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à.
Wow, geniale! :o
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Avatar utente
L Lawliet
Messaggi: 13
Iscritto il: 24 mag 2010, 20:04
Località: Wammy's House

Re: Luca e i suoi strani amici

Messaggio da L Lawliet »

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}$
"Mangiano solo mele, L, lo sai che gli shinigami, hanno le mani rosse?"
Avatar utente
Nonno Bassotto
Site Admin
Messaggi: 970
Iscritto il: 14 mag 2006, 17:51
Località: Paris
Contatta:

Re: Luca e i suoi strani amici

Messaggio da Nonno Bassotto »

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. $
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill
Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: Luca e i suoi strani amici

Messaggio da Mist »

ne approfitto per uppare un poco questo... Il secondo è una generalizzazione della sommatoria che si è dovuta risolvere in questo problema :D

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
Rispondi