OliForum Matematico

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?

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

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

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) $

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

Prova a vedere ora, ho modificato qualcosa

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)

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?

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? ^^'

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...

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?

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} $.

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 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)

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...

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.