Ammissione SNS 2007-2008 es. 1
Salve a tutti, nell'allenarmi ho risolto (credo bene) un problema di ammissione alla normale e, visto che non c'era già, ve lo posto.
Per completezza riporto il testo dell'esercizio aa 07-08 n. 1
Un turista parte per un viaggio di 800km in autostrada; alla partenza ha
fatto il pieno di carburante, e con il pieno ha un’autonomia di 200km;
ma, a causa di uno sciopero, i distributori di benzina hanno una probabilità
del 50% di essere chiusi; lungo l’autostrada il turista troverà un
distributore ogni 100km, e, se il distributore sarà aperto, ogni volta farà
il pieno. Che probabilità ha il turista di arrivare a destinazione? (Nota:
per “probabilità” si intende il rapporto fra il numero dei casi favorevoli
e il numero totale dei casi)
Ho ragionato così: il turista arriva a destinazione se non si ferma senza benzina al 7° distributore, indipendentemente dallo stato dell'8°.
Il turista si ferma se incontra due distributori chiusi di seguito.
Scrivo i sette distributori che studio come un numero di 7 cifre in codice binario, ogni cifra ne rappresenta lo stato: 1= aperto 0 = chiuso.
Con [tex]\[2^7\][/tex] numeri descrivo tutti i casi possibili (ciascuno equiprobabile). Mi propongo di calcolare i casi sfavorevoli.
Definisco "speculare" di un numero (che rappresenta uno stato dei distributori) il numero per cui sostituisco agli 0 1 e agli 1 0 es. speculare di 001 è 110 e distinguo tutti i casi possibili in 3 gruppi:
1) Per ogni numero che contiene almeno una coppia di 0 e non contiene una coppia di 1 (fa fermare il turista) il suo speculare non lo fa fermare
2) Per ogni numero che contiene almeno una coppia di 0 e almeno una coppia di 1 (fa fermare il turista) anche il suo speculare lo fa fermare
3) Per ogni numero che non contiene né una coppia di 0 né una coppia di 1 (non fa fermare il turista) anche il suo speculare non lo fa fermare
si nota subito che quelli di tipo 3 sono solo 2 (0101010 e il suo speculare)
Posso definire il numero N di casi favorevoli per un numero di n cifre come
[tex]\[N = \frac{2^n-(f+c)}{2}+c[/tex]
dove [tex]\[2^n\][/tex] sono i casi totali, c i casi di tipo 2, f i casi di tipo 3
Ho già detto che f = 2, resta c.
I casi di tipo 2 cominciano a comparire da n=4 in su nei casi 0011 e 1100 (speculare)
Da questi due derivano i successivi per n>4, ogni volta che n aumenta di 1, c raddoppia.
Es.:
n = 4 => 0011 1100
n = 5 => 00110 11000
00111 11001
Quindi la formula che determina c, valida per [tex]\[n\geq 4\][/tex] è [tex]\[c = 2^{n-3}\][/tex]
Con un po' di conti (spero giusti) si arriva a dire che i casi contrari sono dati da
[tex]\[N = 2^{n-1}+2^{n-4}-1\][/tex]
e che di conseguenza la probabilità di arrivare è data da
[tex]\[P = 2^{-n}+\frac{7}{16}\][/tex]
Per n = 7 abbiamo che P = 44,5 % circa.
Che ve ne pare?
Per completezza riporto il testo dell'esercizio aa 07-08 n. 1
Un turista parte per un viaggio di 800km in autostrada; alla partenza ha
fatto il pieno di carburante, e con il pieno ha un’autonomia di 200km;
ma, a causa di uno sciopero, i distributori di benzina hanno una probabilità
del 50% di essere chiusi; lungo l’autostrada il turista troverà un
distributore ogni 100km, e, se il distributore sarà aperto, ogni volta farà
il pieno. Che probabilità ha il turista di arrivare a destinazione? (Nota:
per “probabilità” si intende il rapporto fra il numero dei casi favorevoli
e il numero totale dei casi)
Ho ragionato così: il turista arriva a destinazione se non si ferma senza benzina al 7° distributore, indipendentemente dallo stato dell'8°.
Il turista si ferma se incontra due distributori chiusi di seguito.
Scrivo i sette distributori che studio come un numero di 7 cifre in codice binario, ogni cifra ne rappresenta lo stato: 1= aperto 0 = chiuso.
Con [tex]\[2^7\][/tex] numeri descrivo tutti i casi possibili (ciascuno equiprobabile). Mi propongo di calcolare i casi sfavorevoli.
Definisco "speculare" di un numero (che rappresenta uno stato dei distributori) il numero per cui sostituisco agli 0 1 e agli 1 0 es. speculare di 001 è 110 e distinguo tutti i casi possibili in 3 gruppi:
1) Per ogni numero che contiene almeno una coppia di 0 e non contiene una coppia di 1 (fa fermare il turista) il suo speculare non lo fa fermare
2) Per ogni numero che contiene almeno una coppia di 0 e almeno una coppia di 1 (fa fermare il turista) anche il suo speculare lo fa fermare
3) Per ogni numero che non contiene né una coppia di 0 né una coppia di 1 (non fa fermare il turista) anche il suo speculare non lo fa fermare
si nota subito che quelli di tipo 3 sono solo 2 (0101010 e il suo speculare)
Posso definire il numero N di casi favorevoli per un numero di n cifre come
[tex]\[N = \frac{2^n-(f+c)}{2}+c[/tex]
dove [tex]\[2^n\][/tex] sono i casi totali, c i casi di tipo 2, f i casi di tipo 3
Ho già detto che f = 2, resta c.
I casi di tipo 2 cominciano a comparire da n=4 in su nei casi 0011 e 1100 (speculare)
Da questi due derivano i successivi per n>4, ogni volta che n aumenta di 1, c raddoppia.
Es.:
n = 4 => 0011 1100
n = 5 => 00110 11000
00111 11001
Quindi la formula che determina c, valida per [tex]\[n\geq 4\][/tex] è [tex]\[c = 2^{n-3}\][/tex]
Con un po' di conti (spero giusti) si arriva a dire che i casi contrari sono dati da
[tex]\[N = 2^{n-1}+2^{n-4}-1\][/tex]
e che di conseguenza la probabilità di arrivare è data da
[tex]\[P = 2^{-n}+\frac{7}{16}\][/tex]
Per n = 7 abbiamo che P = 44,5 % circa.
Che ve ne pare?
Risposte
"koss":
I casi di tipo 2 cominciano a comparire da n=4 in su nei casi 0011 e 1100 (speculare)
Da questi due derivano i successivi per n>4, ogni volta che n aumenta di 1, c raddoppia.
Es.:
n = 4 => 0011 1100
n = 5 => 00110 11000
00111 11001
Quindi la formula che determina c, valida per [tex]\[n\geq 4\][/tex] è [tex]\[c = 2^{n-3}\][/tex]
ma come fai a esserne sicuro? hai provato solo due casi, non c'è un accenno di dimostrazione.
Hai ragione, e tra l'altro ho anche sbagliato a considerare per n = 5 perché i casi di tipo 2 sono più di 4!
0011-0
0011-1
00-0-11
00-1-11
0-0011
1-0011
e speculari.
Tento di risolvere ora: l'appartenenza al gruppo 2 è data dall'esistenza nel numero di ALMENO una coppia di 1 e di ALMENO una coppia di 0.
In pratica si tratta di calcolare il numero di permutazioni possibili di un insieme di n-2 elementi (perché le coppie si comportano come un elemento unico essendo inscindibili) e di moltiplicare per i modi in cui possono variare le n-4 cifre che non determinano l'appartenenza al gruppo 2. Le n-4 cifre possono essere disposte in [tex]\[2^{n-4}\][/tex] modi diversi. Quindi in definitiva
[tex]\[c = (n-2)! *2^{n-4}\][/tex]
dopodiché sono conti. Grazie della correzione
Ora torna tutto?
0011-0
0011-1
00-0-11
00-1-11
0-0011
1-0011
e speculari.
Tento di risolvere ora: l'appartenenza al gruppo 2 è data dall'esistenza nel numero di ALMENO una coppia di 1 e di ALMENO una coppia di 0.
In pratica si tratta di calcolare il numero di permutazioni possibili di un insieme di n-2 elementi (perché le coppie si comportano come un elemento unico essendo inscindibili) e di moltiplicare per i modi in cui possono variare le n-4 cifre che non determinano l'appartenenza al gruppo 2. Le n-4 cifre possono essere disposte in [tex]\[2^{n-4}\][/tex] modi diversi. Quindi in definitiva
[tex]\[c = (n-2)! *2^{n-4}\][/tex]
dopodiché sono conti. Grazie della correzione
Ora torna tutto?
a me pare un buon ragionamento, l'idea di usare un numero in binario è quella vincente.
quindi direi che hai fatto un buon esercizio.
sul risultato però ho un piccolo dubbio: tu trovi (prima di accorgerti di un errore è vero, ma non credo che cambi sostanzialmente)
$P=2^(-n)+7/16$
è strano che al tendere di $n$ a $infty$ la probabilità non tenda a $0$. è quello che mi aspetterei, ma niente di più, non ho vere prove per supportare la mia intuizione.
cosa ne pensi?
quindi direi che hai fatto un buon esercizio.
sul risultato però ho un piccolo dubbio: tu trovi (prima di accorgerti di un errore è vero, ma non credo che cambi sostanzialmente)
$P=2^(-n)+7/16$
è strano che al tendere di $n$ a $infty$ la probabilità non tenda a $0$. è quello che mi aspetterei, ma niente di più, non ho vere prove per supportare la mia intuizione.
cosa ne pensi?
Sì, in effetti è strano non posso darti torto. Per definizione la probabilità è casi favorevoli su casi totali quindi eccola la spiegazione! Poteva essere un buon sistema per scoprire che c'era un errore.
A proposito, mi hai messo la pulce nell'orecchio e sono andato a fare un po' di grafici con derive di queste nuove soluzioni che ho trovato. Ho visto che la curva di [tex]y = 2^{n}[/tex] e quella che descrive c in funzione di n hanno un'intersezione circa a n=6
Non ha senso, vorrebbe dire che esiste un punto in cui i casi di tipo 2 sono più dei casi totali!! O c'è un errore nel mio ragionamento oppure non so usare derive... Propenderei per l'errore, ma dove?
A proposito, mi hai messo la pulce nell'orecchio e sono andato a fare un po' di grafici con derive di queste nuove soluzioni che ho trovato. Ho visto che la curva di [tex]y = 2^{n}[/tex] e quella che descrive c in funzione di n hanno un'intersezione circa a n=6
Non ha senso, vorrebbe dire che esiste un punto in cui i casi di tipo 2 sono più dei casi totali!! O c'è un errore nel mio ragionamento oppure non so usare derive... Propenderei per l'errore, ma dove?
non ho letto il tuo ragionamento, ma sappi che il risultato giusto per $n\ge 1$ è $\frac{F_{n+2}}{2^{n-1}}$ dove $F_n$ indica l'n-esimo numero di fibonacci (con $F_0=0$,$F_1=1$) che effettivamente tende a 0 se n tende a infinito.
P.S: tra l'altro grazie a questo problema ho scoperto una curiosa identità sui binomiali:
$\sum_{i=0}^{[\frac n 2]}\frac{(n-i)!}{i!(n-2i)!}=F_{n+2}$
P.S: tra l'altro grazie a questo problema ho scoperto una curiosa identità sui binomiali:
$\sum_{i=0}^{[\frac n 2]}\frac{(n-i)!}{i!(n-2i)!}=F_{n+2}$
"Gaussman":
non ho letto il tuo ragionamento, ma sappi che il risultato giusto per $n\ge 1$ è $\frac{F_{n+2}}{2^{n-1}}$ dove $F_n$ indica l'n-esimo numero di fibonacci (con $F_0=0$,$F_1=1$) che effettivamente tende a 0 se n tende a infinito.
ok che tende a 0 se n tende a infinito ma perché è la soluzione al problema?
Edit: ho calcolato la soluzione con un programmino in C che ho preparato e la tua formula non dà esattamente lo stesso risultato. Io ho ottenuto 34 casi favorevoli, $ P = 0.265 $
Con la tua formula verrebbe $ P = 15/64 = 0.234 $
guarda che $\frac{F_{10}}{2^7}=\frac{34}{128}=0,265$ 
quindi il risultato è corretto. Comunque se sei agli inizi ti consiglio di lasciar perdere il problema per n generico (poi volendo posso anche scriverti la soluzione se proprio ti interessa) e risolverlo per come è dato, cioè per n=8 e basta che è infinitamente più semplice
quindi il risultato è corretto. Comunque se sei agli inizi ti consiglio di lasciar perdere il problema per n generico (poi volendo posso anche scriverti la soluzione se proprio ti interessa) e risolverlo per come è dato, cioè per n=8 e basta che è infinitamente più semplice
"Gaussman":
guarda che $\frac{F_{10}}{2^7}=\frac{34}{128}=0,265$
quindi il risultato è corretto. Comunque se sei agli inizi ti consiglio di lasciar perdere il problema per n generico (poi volendo posso anche scriverti la soluzione se proprio ti interessa) e risolverlo per come è dato, cioè per n=8 e basta che è infinitamente più semplice
ma noo!!! colpa mia, ho sbagliato a leggere la formula e ho preso $ F_{n+2} $ per $ F_{n}+2 $ e non capivo!
Seguirò il tuo consiglio e mi metterò a risolvere per n=8, magari una volta arrivato alla soluzione poi riesco a generalizzare. Se ancora non arrivo da nessuna parte comunque mi interessa la soluzione
la soluzione generale interssa a tutti, quindi Gaussman ti chiedo di postarla qui!
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!
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!
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}$
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}$
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.
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.
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.
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.
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
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
Propongo la mia soluzione:
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo