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 » 04 ott 2011, 17:15

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: 63
Iscritto il: 22 nov 2010, 15:14
Località: Lunghezza

Re: Luca e i suoi strani amici

Messaggio da ale.G » 04 ott 2011, 17:44

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: 1139
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Luca e i suoi strani amici

Messaggio da Drago96 » 04 ott 2011, 18:26

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 » 05 ott 2011, 15:43

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 » 05 ott 2011, 15:51

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: 1139
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Luca e i suoi strani amici

Messaggio da Drago96 » 05 ott 2011, 17:03

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 » 05 ott 2011, 17:41

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> » 05 ott 2011, 17:47

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: 471
Iscritto il: 22 giu 2011, 21:51

Re: Luca e i suoi strani amici

Messaggio da xXStephXx » 05 ott 2011, 17:57

Fico è geniale quell'approccio :mrgreen: E chi ci avrebbe pensato? xD

Avatar utente
Drago96
Messaggi: 1139
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Luca e i suoi strani amici

Messaggio da Drago96 » 05 ott 2011, 18:04

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: 471
Iscritto il: 22 giu 2011, 21:51

Re: Luca e i suoi strani amici

Messaggio da xXStephXx » 05 ott 2011, 18:07

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: 1139
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Luca e i suoi strani amici

Messaggio da Drago96 » 05 ott 2011, 18:09

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 » 06 ott 2011, 18:13

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 » 07 ott 2011, 02:24

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 » 07 ott 2011, 20:12

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