lampadine consecutive accese

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Veluca
Messaggi: 185
Iscritto il: 27 dic 2008, 01:08
Località: Chiavari (Genova)

lampadine consecutive accese

Messaggio da Veluca » 27 dic 2008, 01:13

dato n un numero di lampadine ognuna puo essere spenta o accesa con la probabilità di $ \frac{1}{2} $. Qual'è la probabilità (espressa in funzione di n, non ricorsivamente) che vi siano almeno 2 lampadine accese consecutive?

Avatar utente
iademarco
Messaggi: 264
Iscritto il: 10 dic 2008, 22:12
Località: Campobasso

Messaggio da iademarco » 27 dic 2008, 15:54

se non sbaglio dovrebbe essere [(2 alla n-1)-1] / (2 alla n). scusate se l'ho scritto un po' così "alla brutta", ma non so usare il latex :oops:

Veluca
Messaggi: 185
Iscritto il: 27 dic 2008, 01:08
Località: Chiavari (Genova)

Messaggio da Veluca » 27 dic 2008, 16:04

\frac{2^{n-1}-1}{2^n}
$ \frac{2^{n-1}-1}{2^n} $
comunque, di giusto c'è solo il denominatore XD

String
Messaggi: 225
Iscritto il: 01 giu 2008, 17:21

Messaggio da String » 27 dic 2008, 21:34

ll numeratore potrebbe essere per caso
con n pari

$ \displaystyle \binom {n}{0}+\binom {n}{1}+\cdots+\binom {n}{\frac {n}{2}-1}+n-1+\binom {n-2}{1}+\binom {n-2}{2}+\cdots +\binom {n-2}{\frac {n}{2}-2}+(n-2)\cdot \left( \binom {n-3}{1}+ \binom {n-3}{2}+\cdots + \binom {n-3}{\frac {n}{2}-2}\right) $

oppure con n dispari

$ \displaystyle \binom {n}{0}+\binom {n}{1}+\cdots+\binom {n}{\frac {n-1}{2}-1}+n-1+\binom {n-2}{1}+\binom {n-2}{2}+\cdots +\binom {n-2}{\frac {n+1}{2}-2}+(n-2)\cdot \left( \binom {n-3}{1}+ \binom {n-3}{2}+\cdots + \binom {n-3}{\frac {n+1}{2}-2}\right) $

:?:
Ultima modifica di String il 27 dic 2008, 23:10, modificato 1 volta in totale.
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)

Veluca
Messaggi: 185
Iscritto il: 27 dic 2008, 01:08
Località: Chiavari (Genova)

Messaggio da Veluca » 27 dic 2008, 22:38

se quel coso deve dare i casi possibili, non credo proprio ^^ vengono numeri TROPPO alti
edit: grammatica -.-''

String
Messaggi: 225
Iscritto il: 01 giu 2008, 17:21

Messaggio da String » 27 dic 2008, 23:11

Prova a vedere ora, ho modificato qualcosa
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)

Veluca
Messaggi: 185
Iscritto il: 27 dic 2008, 01:08
Località: Chiavari (Genova)

Messaggio da Veluca » 28 dic 2008, 00:17

no, dà comunque valori troppo grandi...
se per esempio n fosse 3,verrebbe >3 (mi son fermato a n-1) mentre dovrebbe venire 3... (spero di non aver toppato xD)

Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 600
Iscritto il: 01 gen 1970, 01:00
Località: Pisa
Contatta:

Messaggio da FrancescoVeneziano » 28 dic 2008, 01:08

Ma siamo su un forum di matematica o da Mike Bongiorno?
Invece di tirare numeri a caso perché non spiegate per bene la dimostrazione? Il solo atto di scrivere la dimostrazione aiuta ad individuare errori che possono essere sfuggiti in prima battuta; se scrivete solo un numero non avete fatto nulla.

Veluca, non sarebbe bello se questo problema avesse un testo chiaro, comprensibile e non ambiguo?
Wir müssen wissen. Wir werden wissen.

Veluca
Messaggi: 185
Iscritto il: 27 dic 2008, 01:08
Località: Chiavari (Genova)

Messaggio da Veluca » 28 dic 2008, 01:12

FrancescoVeneziano ha scritto:Veluca, non sarebbe bello se questo problema avesse un testo chiaro, comprensibile e non ambiguo?
Scusa la domanda ma... cosa c'è che non va nel testo? ^^'

String
Messaggi: 225
Iscritto il: 01 giu 2008, 17:21

Messaggio da String » 28 dic 2008, 09:31

Veluca ha scritto:no, dà comunque valori troppo grandi...
se per esempio n fosse 3,verrebbe >3 (mi son fermato a n-1) mentre dovrebbe venire 3... (spero di non aver toppato xD)
Se $ n=3 $ allora si ha
$ \displaystyle \binom {n}{0} +n-1=3 $
Comunque scrivo il procedimento più tardi, ora non ho tempo...
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)

String
Messaggi: 225
Iscritto il: 01 giu 2008, 17:21

Messaggio da String » 28 dic 2008, 12:00

Allora, ci possono essere $ n-1 $ casi con sole 2 lampadine accese. Nel caso in cui $ n $ sia pari allora se ci sono più di $ $ \frac {n}{2} $ lampadine accese, ci sarà almeno una coppia di lampadine consecutive accese. Perciò per contare il numero di casi possibilli con più di $ $ \frac {n}{2} $ lampadine accese possiamo considerare in quanti modi possiamo lasciarne spente $ $ 0,1,2\dots \frac {n}{2}-1 $, da cui
$ $ \binom {n}{0}+\binom {n}{1}+\cdots +\binom {n}{\displaystyle \frac {n}{2}-1} $
Immaginiamo ora di accendere le prime due lampadine. Se ne voglio accendere un'altra, questa potrà essere la terza, la quarta,ecc, cioè ci sono $ $ \binom {n-2}{1} $ casi possibili
Accendiamo ora solo la seconda e la terza lampadina. Ne vogliamo accendere un'altra. Questa potrà essere la quarta,la quinta,ecc, ma non la prima in quanto questo comporterebbe le prime tre lampadine accese, che abbiamo già contato prima. Quindi sono possibili $ $ \binom {n-3}{1} $ casi. Accendiamo ora la terza e la quarta. L'altra lampadina accesa potrà essere la quinta, la sesta, la prima, ma non la seconda perchè questo caso l'abbiamo già contato.Si va avanti così fino a contare i casi con tre lampadine accese con le due consecutive in tutte le $ n-1 $ posizioni possibili. Quindi i casi con 3 lampadine accese sono
$ $ \binom {n-2}{1}+(n-2)\cdot \binom {n-3}{1} $.
Se ne vogliamo accendere quattro, cinque, seguo lo stesso procedimento di prima fino ad arrivare a $ $ \frac {n}{2} $ lampadine accese.
Nel caso in cui $ n $ sia dispari il minimo numero di lampadine accese tali che almeno due di esse siano consecutive è $ $ \frac {n+1}{2}+1 $. Perciò potrò contare direttamente i modi in cui ne posso lasciare spente $ $ 0,1,2\dots \frac {n-1}{2}-1 $. Poi seguo lo stesso ragionamento di prima fino a contare il numero di casi con $ $ \frac {n+1}{2} $ lampadine accese.
Non so se sono stato abbastanza chiaro, c'è per caso qualche errore?
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 28 dic 2008, 13:09

ENNESIMO EDIT: ora dovrebbe funzionare
$ $\frac{2^n-\displaystyle\sum_{a=0}^\frac{n}{2}{n-a-1\choose n-2a+1}+2{n-a-1\choose n-2a}+{n-a-1\choose n-2a-1}}{2^n}$ $ o $ $\frac{2^n-\displaystyle\sum_{a=0}^\frac{n-1}{2}{n-a-1\choose n-2a+1}+2{n-a-1\choose n-2a}+{n-a-1\choose n-2a-1}-1}{2^n}$ $, a seconda che n sia pari o dispari.
Semplificato diventa:
$ $\frac{2^n-\displaystyle\sum_{a=0}^\frac{n}{2}\frac{(n^2+a^2-2an+n+a)(n-a-1)!}{a!(n-2a+1)!}}{2^n}$ $ o $ $\frac{2^n-\displaystyle\sum_{a=0}^\frac{n-1}{2}\frac{(n^2+a^2-2an+n+a)(n-a-1)!}{a!(n-2a+1)!}-1}{2^n}$ $
In pratica cerco la probabilità che non ci siano coppie di lampadine accese:
per questo a una lampadina accesa ne deve seguire una spenta (a meno che questa sia in fondo); chiamo a il numero di coppie accesa-spenta (ma non spenta-accesa) e s il numero di lampadine spente;
si deve avere $ $2a+s = n$ $, con $ a = 0,\dots,\frac{n}{2} $ (o $ a = 0,\dots,\frac{n-1}{2} $ se n dispari).
Ora, la successione di lampadine può essere vista come una serie di blocchi accesa-spenta e di lampadine spente.
Distinguiamo tre casi:
- l'ultimo elemento è un "a": i modi di mettere gli "s" sarebbero $ {n-a-1\choose n-2a} $, ma per considerare anche il caso dell'ultima lampadina accesa dobbiamo moltiplicare per 2 (per ottenere un blocco spenta-accesa) (v. anche ultimo caso);
- l'ultimo elemento non è un "a": non si pone il problema di prima e possiamo subito dire che il numero di modi di sistemare gli "s" sono $ {n-a-1\choose n-2a-1} $;
- l'ultimo elemento è un blocco accesa-spenta-accesa: (equivalente a dire che gli ultimi due "a" si fondono) i modi di posizionare gli "s" sono $ {n-a-1\choose n-2a-1} $; per n dispari anche $ a = \frac{n-1}{2}+1 $ produce questo caso, quindi bisogna aggiungere 1 (ovvero la combinazione accesa-spenta-accesa-...-spenta-accesa)
Sommandoli e facendo variare a si ottiene quella somma mostruosa.
La probabilità richiesta è complementare a $ \frac{somma}{2^n} $.
Ultima modifica di kn il 28 dic 2008, 18:02, modificato 5 volte in totale.

Veluca
Messaggi: 185
Iscritto il: 27 dic 2008, 01:08
Località: Chiavari (Genova)

Messaggio da Veluca » 28 dic 2008, 13:10

ah... in effetti il ragionamento sembra giusto...
ho controllato a mente fino a n=6 e viene, credo che far controllare al pc sia la cosa migliore XD (dammi 20 minuti e lo faccio)
comunque se questo metodo funziona siamo arrivati a 3 modi diversi :D vediamo se qualcuno trova gli altri due...
edit: non ho visto il messaggio precedente... dammi un po' di tempo e controllo anche quello
edit2: la prima è sbagliata, oppure io ho sbagliato il programma: con 1,3,4,5,6 funziona, ma con gli altri no
edit3: la seconda anche, il ragionamento sembra giusto, ma fino a 6 dà risultati sbagliati, e da 7 in poi dà addirittura risultati negativi (oppure sono io che non so leggere la tua formula XD)

Avatar utente
mod_2
Messaggi: 726
Iscritto il: 18 ago 2007, 20:26
Località: In fondo a destra

Messaggio da mod_2 » 28 dic 2008, 17:20

Bò, dico anche la mia...

Definiamo adesso $ $S(n)$ $ le configurazioni sfavorevoli con n lampadine, e $ F(n) $ quelli favorevoli (che è naturalmente uguale a $ $2^n-S(n)$ $)

Per n=2
configurazioni possibili:
AA
AS
SA
SS
(A=accesa; S=spenta)
$ $S(2)=3$ $; $ F(2)=2^2-3=1 $

Per n=3
configurazioni possibili
AAA
AAS
ASA
SAA
ASS
SAS
SSA
SSS
$ $S(3)=5$ $; $ F(3)=2^3-5=3 $

Supponiamo ora di conoscere $ $S(i)$ $ per tutti gli $ $i<n$ $ e vogliamo calcolare $ $S(n)$ $. le n lampadine possono essere viste come una fila di n-1 lampadine +1 lampadina. Quest'ultima piò essere accesa o spenta da cui abbiamo due casi:

Spenta: se è spenta allora i casi sfavorevoli sono uguali a $ $S(n-1)$ $.

Accesa: se è accesa l'ultima allora la penultima non può essere accesa, in altre parole la penultima resta determinata e quindi basta contare i $ $S(n-2)$ $

In conclusione $ $S(n)=S(n-1)+S(n-2)$ $ wuao! Fibonacci!

La probabilità cercata è quindi $ $\dfrac{2^n-F_{n+2}}{2^n}$ $ dove $ $F_{n+2}$ $ è l'n+2 esimo numero di Fibonacci.

A voi la correzione

EDIT: appena letto la dimostrazione di kn, e mi son accorto che abbiamo scritto più o meno la stessa cosa...
Appassionatamente BTA 197!

Avatar utente
Ratio
Messaggi: 62
Iscritto il: 29 nov 2007, 20:22
Località: Una realtà quadridimensionale (forse)

Messaggio da Ratio » 28 dic 2008, 18:12

Anch'io ho cercato la probabilità complementare, e come formula risolutiva è uscita:
$ P(n) = 1-\displaystyle\frac{1+\displaystyle\sum_{k=1}^{\frac{n}{2}}{n-2k+1\choose k}}{2^n} $ per pari e $ P(n) = 1-\displaystyle\frac{1+\displaystyle\sum_{k=1}^{\frac{n-1}{2}}{n-2k+1\choose k}}{2^n} $ per dispari.
L'unica differenza nel calcolo è che prendo in considerazione le disposizioni dei vuoti tra le lampadine accese, la cui somma è un invariante.
"L'apprendere molte cose non insegna l'intelligenza"
Eraclito

Rispondi