ammissione SNS 2007-2008 es. 1

[Gaussman]

Credo che questo sia il modo più semplice di vederlo:
sia $P_n$ la probabilità di arrivare alla fine di un percorso di n tacche (e n-1 serbatoi).
Ora voglio trovare una ricorrenza per $P_n$:
inizio col notare che tra gli ultimi 2 distributori, almeno 1 deve essere aperto, quindi ho 3 casi favorevoli che si verificano con probabilità 1/4 ciascuno:
aperto-aperto
chiuso-aperto
aperto-chiuso

se l'ultimo serbatoio è aperto (il che succede nei primi 2 casi, e quindi ho probabilità 1/2 che succeda) allora la probabilità di arrivare alla fine è uguale a 1/2*(probabilità di arrivare all'ultimo serbatoio)=$1/2P_{n-1}$
Se l'ultimo serbatoio è chiuso e il penultimo è aperto (caso 3, quindi succede con probabilità 1/4) allora la probabilità di arrivare alla fine è uguale a 1/4*(probabilità di arrivare al penultimo serbatoio)=$1/4P_{n-2}$

Quindi in conclusione $P_n=1/2P_{n-1}+1/4P_{n-2}$, con $P_1=1$,$P_2=1$
Ora se vogliamo anche verificare il fatto che i casi favorevoli soddisfano fibonacci, ricordiamo che la probabilità è il rapporto tra casi favorevoli e casi possibili, quindi chiamati $C_n$ i casi favorevoli abbiamo $P_n=\frac{C_n}{2^{n-1}}$.

Sostituiamo nella precedente relazione e abbiamo $C_n=C_{n-1}+C_{n-2}$, come volevasi dimostrare.
Spero che si capisca, se qualcosa non è chiaro chiedete pure!

[Umby]

Si potrebbe anche generalizzare, con un serbatoio, ad esempio, capace di garantire 300 Km ( e quindi 3 step, anzichè 2).

In questo caso utilizziamo la serie di Tribonacci:
0, 1, 1, 2, 4, 7, 13, 24, 44, 81

$C_n=C_{n-1}+C_{n-2}+C_{n-3}$

[fra_pozz]

Credo che la soluzione sia $ \( \binom{4}{4} +\binom{5}{3} + \binom {6}{2} + \binom{7}{1} + \binom {8}{0} \) , riscrivibile come $\sum_{k=0}^\4$ \(\binom{4+k}{4-k}\) ; tutto naturalmente diviso $2^7$ per ottenere la probabilità

Ho considerato separatamente i casi in cui tra i sette distributori ve ne siano 0,1,2,3,4 non funzionanti (di più è impossibile, ve ne sarebbero almeno due consecutivi), e tutti i modi per distribuirli tra quelli funzionanti con la limitazione che non posso trovarne due consecutivi chiusi.

[lorenzom97]

La soluzione che ho trovato è ricorsiva (sicuramente non è elegante quanto quella di Gaussman):
la funzione (ricorsiva) che ho trovato calcola il numero totali di casi sfavorevoli per un numero N (>2) di distributori. I casi sfavorevoli sono quelle sequenze ( di 0 e 1) che presentano almeno una coppia di 0. Quindi, la mia soluzione prende i casi minimi di fallimento (Es: 00xxxxx, 100xxxx, x100xxx, xx100xx, etc) e vede tutte le combinazioni degli elementi(x) che rendono la sequenza lo stesso fallimentare, ma diversa da quelle precedenti. La formula è:

\[f(N)=2^{N-2}+\sum_{i=0}^{N-3} 2^{N-3-i}(2^i-f(i))\]

con \(f(0)=f(1)=0\).
\(2^{N-3-i}\) rappresenta il numero totale di possibili sequenze che seguono la sequenza fallimentare (100), mentre \((2^i-f(i))\) rappresenta il numero di di sequenze favorevoli ( numero totale di casi (\(2^{i}\)) meno il numero di casi fallimentari (\(f(i)\)) )che precedono la sequenza fallimentare(100).

Quindi per N=7, la soluzione sarà \[P=1-\frac{f(7)}{2^7}\]

PS: la mia soluzione rientra nel caso di Gaussman, in quanto, definendo con \(F(N\)) la funzione che restituisce il numero di sequenze di N cifre favorevoli (\(2^N-f(N)\)) è dimostrabile che \(F(N)=F(N-1)+F(N-2)\). Quindi è una sequenza di Fibonacci.

[tiz97]

Da premettere che non ho letto tutta la discussione
Ho voluto costruire un diagramma della situazione, e se non ho sbagliato a contare si dovrebbe trattare di 79 casi fallimentari contro 49 favorevoli su un totale di 128 casi.
Dunque la soluzione, data così empiricamente, dovrebbe essere

P = 49/128 = 0,38 c.ca

Sempre che non mi sia confuso nel calcolo

[.Ruben.]

Propongo la mia soluzione:

Testo nascosto, fai click qui per vederlo

Ho dei codici binari di $7$ cifre, devo contare quanti non hanno due zeri consecutivi.
Inizio da un codice di n cifre e poi generalizzo..
se $n = 1$ allora i codici sono $1$ e $0$
Quando passo ad $(n+1)$ aggiungo una cifra a destra di ognuno dei codici favorevoli per n:
aggiungerò un 1 ad ognuno dei codici ed aggiungerò uno $0$ solo ai codici che terminano per $1$(così da evitare sempre il doppio zero):
$n=1$ : $1, 0$
$n=2$ : $11, 01, 10$
$n=3$ : $111, 011, 101, 110, 010$

Denomino $a_{n}$ il numero dei codici favorevoli di n cifre
Il numero dei codici di n cifre che finiscono per $1$ è uguale a $a_{n-1}$, mentre il numero dei codici che terminano per $0$ è uguale ad numero dei codici di $(n-1)$ cifre che finiscono per $1$, ossia $a_{n-2}$
Quindi il numero dei codici favorevoli di n cifre è $a_{n}=a_{n-1}+a_{n-2}$
con $a_{1} = 2$ e $a_{2}=3$
Quindi $a_{n}=F_{n+2}$ [considerando nella sequenza di Fibonacci $a_{0}=0$ e $a_{1}=1$]
Il numero dei codici possibili(in totale) di n cifre è banalmente $2^n$

Quindi per $n=7$ si ha: $p_{7} = 34/2^7 = 0.265625$