Problema Ammissione SNS

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Problema Ammissione SNS

Messaggioda Lo_09 » 17/08/2017, 23:18

Salve a tutti, nell'esercitarmi per il test di ammissione alla sns mi sono imbattuto in questo problema (Esercizio 3 prova di ammissione al primo anno per la classe di scienze 2014-15), il testo è quello che segue:

La città di Sapi è una città immaginaria, di estensione infinita. Copre l'intero piano cartesiano; le strade sono le rette orizzontali e verticali di equazione y=n o x= n, dove n è un intero arbitraria Di conseguenza, gli incroci sono precisamente i punti con coordinate intere. Il fiume Orna attraversa la città in diagonale secondo la retta y=x+1/2. Alessia si muove per la città senza fermarsi mai partendo dall'incrocio (0, 0) e procedendo solo verso nord o verso est. • (1) Quanti sono i possibili percorsi che Alessia può effettuare per raggiungere l'incrocio di coordinate (a, b) senza attraversare mai il fiume? (2) Supponiamo che ad ogni incrocio Alessia decida di digersi ad est con probabilità p e verso nord con probabilità q = 1 — p. Dimostrare che la probabilità che Alessia abbia attraversato almeno una volta il fiume dopo essere passata da n incroci è minore o uguale a q/p.

Purtroppo ho provato ad approcciare il problema in vari modi ma non sono riuscito a trovare una soluzione...se qualcuno lo ha già risolto mi spieghi come per favore :!: :!:
Lo_09
 
Messaggi: 9
Iscritto il: 24/07/2017, 14:16

Re: Problema Ammissione SNS

Messaggioda afullo » 18/08/2017, 12:11

Sposto nella sezione più adatta. ;)
afullo
 
Messaggi: 1236
Iscritto il: 13/03/2013, 22:06

Re: Problema Ammissione SNS

Messaggioda Lo_09 » 18/08/2017, 12:13

Okay grazie
Lo_09
 
Messaggi: 9
Iscritto il: 24/07/2017, 14:16

Re: Problema Ammissione SNS

Messaggioda Dudin » 18/08/2017, 18:50

Per il punto 1:
Hint:
Testo nascosto:
Combinatoria semplice

Tra un po' posto la soluzione in spoiler

*ho cambiato l'hint perchè l'altro non serviva
Ultima modifica di Dudin il 19/08/2017, 10:07, modificato 1 volta in totale.
Dudin
 
Messaggi: 90
Iscritto il: 15/02/2017, 14:13

Re: Problema Ammissione SNS

Messaggioda Lo_09 » 18/08/2017, 18:57

Dudin ha scritto:Per il punto 1:
Hint:
Testo nascosto:
Approccio in modo ricorsivo

Tra un po' posto la soluzione in spoiler


Io ho provato ad analizzare il numero di percorsi possibili per andare in un punto, prima sulla retta y=0 poi y=1 ecc. Senza però trovare una formula generale che mi restituisca il numero di percorsi possibili per andare in un dato punto (a;b)
Lo_09
 
Messaggi: 9
Iscritto il: 24/07/2017, 14:16

Re: Problema Ammissione SNS

Messaggioda Dudin » 19/08/2017, 10:06

Ciao scusa il ritardo
comunque ecco la soluzione che ho trovato:
Testo nascosto:
Preso un punto P di coordinate (a,b) con b compreso tra 1 e a (estremi inclusi) il numero di percorsi possibili sono:
[tex]\binom{a+b-1}{a-1} - \binom{a+b-1}{a}[/tex]

*correzione piccolo errore
Ultima modifica di Dudin il 19/08/2017, 11:19, modificato 2 volte in totale.
Dudin
 
Messaggi: 90
Iscritto il: 15/02/2017, 14:13

Re: Problema Ammissione SNS

Messaggioda Lo_09 » 19/08/2017, 10:12

Grazie mille..ma come si ricava?
Lo_09
 
Messaggi: 9
Iscritto il: 24/07/2017, 14:16

Re: Problema Ammissione SNS

Messaggioda Lasker » 19/08/2017, 10:13

Questo esercizio è noto come "problema del ballottaggio", qui dovresti trovare più o meno tutto quello che vuoi sapere https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem... insomma l'esercizio favoriva assai chi conosceva già il procedimento (personalmente mi sembra che fosse conveniente ricordare la soluzione per "riflessione")
Cur enim scribere tre numeri quando se ne abbisogna di due? Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani.

PRIMA FILA TUTTI SBIRRI!

#FREELEPORI
Lasker
 
Messaggi: 758
Iscritto il: 17/03/2013, 16:00

Re: Problema Ammissione SNS

Messaggioda Lo_09 » 19/08/2017, 10:23

Grazie mille!
Lo_09
 
Messaggi: 9
Iscritto il: 24/07/2017, 14:16

Re: Problema Ammissione SNS

Messaggioda Dudin » 19/08/2017, 10:56

Testo nascosto:
I percorsi da contare sono:
percorsi totali - percorsi sbagliati.

Come si calcolano i percorsi totali?
Se il punto ha cordinate (a,b) ovviamente dovremo fare a mosse ad est e b mosse a nord.
Tuttavia la prima mossa è sempre a destra quindi ho fatto finta di partire non dall'origine ma dal punto (1,0) (si poteva fare anche dall'origine però)
Quindi le mosse totali diventano a-1 ad est e b a nord quindi:
[tex]\binom{a+b-1}{a-1}[/tex]

Come si calcolano i percorsi sbagliati?

Prendiamo il punto P' di coordinate (b-1,a).
I percorsi sbagliati sono quelli che partono dal punto (1,0) e arrivano a P' cioè
[tex]\binom{a+b-1}{a}[/tex]
Perche?
I percorsi sbagliati toccano il fiume arrivando in una coordinata compresa tra (1,2) e (b-1;b) (incluse) Infatti tutti i percorsi che vanno a P' toccano passano almeno in uno di quei punti.
Inoltre una volta toccato il punto oltre al fiume Bisogna aggiungere tutti i percorsi che vanno del punto oltre al fiume al punto di arrivo
(che sono le stesse che vanno dal punto oltre al fiume a P').

In altre parole tracciando una retta che passa per i punti subito dopo il fiume (0,1) (1,2) (2,2)... stiamo prendendo il simmetrico del punto di arrivo rispetto a quella retta.

ps non so se sono riuscito a spiegarmi bene ma puoi guardarti un video senior di combinatoria dove la cosa viene spiegata meglio
Dudin
 
Messaggi: 90
Iscritto il: 15/02/2017, 14:13

Prossimo

Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti