Numero percorsi (Problema SNS 2014)

[consec]

La città di Sapi è una città immaginaria, di estensione infinita. Copre l'intero piano cartesiano; le strade sono le rette orizzontali e verticali di equazioni y = n o x = n, dove n è un intero arbitrario. 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 e verso est.
- Quanti sono i possibili percorsi che Alessia può effettuare per raggiungere l'incrocio di coordinate (a,b) senza mai attraversare il fiume?
- Supponiamo che ad ogni incrocio Alessia decida di dirigersi 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.

[Vincent46]

"consec":La città di Sapi è una città immaginaria, di estensione infinita. Copre l'intero piano cartesiano; le strade sono le rette orizzontali e verticali di equazioni y = n o x = n, dove n è un intero arbitrario. 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 e verso est.
- Quanti sono i possibili percorsi che Alessia può effettuare per raggiungere l'incrocio di coordinate (a,b) senza mai attraversare il fiume?
- Supponiamo che ad ogni incrocio Alessia decida di dirigersi 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.

Provo a dare una soluzione della prima parte.

Per la prima parte, definiamo "cammino" un percorso fra l'origine e un generico punto compostosolo da tratti unitari diretti a est oppure a nord. Osserivamo che la richiesta è di trovare il numero di cammini che arrivano al punto $(a,b)$ senza mai superare la bisettrice del quadrante, ovvero senza mai toccare la retta $r: y=x+1$.

Consideriamo un generico cammino che arriva in $(a,b)$, anche toccando $r$. Se il cammino tocca $r$, procediamo in questo modo: nella porzione di cammino che avviene dopo il contatto, trasformiamo ogni passo ad est in un passo a nord e viceversa, ossia riflettiamo rispetto a $r$ la suddetta porzione di cammino.

Se supponiamo che il contatto con $r$ sia avvenuto nel punto $(x,x+1)$, allora la porzione restante di cammino (prima della riflessione) doveva contare in totale altri $a-x$ passi ad est e altri $b-x-1$ passsi a nord. Poiché dopo la riflessione abbiamo scambiato i passi ad est con quelli a nord, allora la suddetta porzione di cammino, una volta riflessa, conterà esattamente altri $b-x-1$ passi ad est e $a-x$ passi a nord, ovvero il cammino completo post-riflessione andrà a finire nel punto $(b-1, a+1)$. Allora la suddetta operazione di riflessione è una biezione fra i cammini originali "cattivi" (quelli che toccano il fiume) e i cammini di qualsiasi tipo fra l'origine e il punto $(b-1, a+1)$. Dunque i cammini cattivi da escludere sono esattamente $((a+b),(a+1)) $, cioé i modi di scegliere $a+1$ passi diretti verso nord sugli $a+b$ passi totali. Siccome il numero di cammini totali fra l'origine e $(a,b)$ sono $((a+b),(a))$, risulta che il numero di cammini cercato è $((a+b),(a))-((a+b),(a+1))$.

In questa risposta non ho discusso i valori possibili dei parametri $a$ e $b$, ma questa formula ne tiene conto da sé. Ad esempio, notiamo che la formula restituisce un numero positivo se e solo se $a \geq b$, come ci aspetteremmo. Se definiamo \binom{a}{a+1} = 0, questa formula tiene anche conto del caso $b=0$.

Non so scrivere i coefficienti binomiali.
Edit: messo a posto, grazie giammaria!

[giammaria2]

"Vincent46":Non so scrivere i coefficienti binomiali.

Ti rispondo solo su questo perché al resto ho dato solo un'occhiata distratta. Se consulti la guida per scrivere le formule alla voce Matrici scopri ad esempio che $((a+b),(a+1))$ si scrive ((a+b),(a+1)).

[consec]

"Vincent46":
Provo a dare una soluzione della prima parte.

Per la prima parte, definiamo "cammino" un percorso fra l'origine e un generico punto compostosolo da tratti unitari diretti a est oppure a nord. Osserivamo che la richiesta è di trovare il numero di cammini che arrivano al punto $(a,b)$ senza mai superare la bisettrice del quadrante, ovvero senza mai toccare la retta $r: y=x+1$.

Consideriamo un generico cammino che arriva in $(a,b)$, anche toccando $r$. Se il cammino tocca $r$, procediamo in questo modo: nella porzione di cammino che avviene dopo il contatto, trasformiamo ogni passo ad est in un passo a nord e viceversa, ossia riflettiamo rispetto a $r$ la suddetta porzione di cammino.

Se supponiamo che il contatto con $r$ sia avvenuto nel punto $(x,x+1)$, allora la porzione restante di cammino (prima della riflessione) doveva contare in totale altri $a-x$ passi ad est e altri $b-x-1$ passsi a nord. Poiché dopo la riflessione abbiamo scambiato i passi ad est con quelli a nord, allora la suddetta porzione di cammino, una volta riflessa, conterà esattamente altri $b-x-1$ passi ad est e $a-x$ passi a nord, ovvero il cammino completo post-riflessione andrà a finire nel punto $(b-1, a+1)$. Allora la suddetta operazione di riflessione è una biezione fra i cammini originali "cattivi" (quelli che toccano il fiume) e i cammini di qualsiasi tipo fra l'origine e il punto $(b-1, a+1)$. Dunque i cammini cattivi da escludere sono esattamente $ \binom[a+b}{a+1} $, cioé i modi di scegliere $a+1$ passi diretti verso nord sugli $a+b$ passi totali. Siccome il numero di cammini totali fra l'origine e $(a,b)$ sono $ \binom {a+b} {a} $, risulta che il numero di cammini cercato è $\binom{a+b}{a}-\binom{a+b}{a+1}$.

In questa risposta non ho discusso i valori possibili dei parametri $a$ e $b$, ma questa formula ne tiene conto da sé. Ad esempio, notiamo che la formula restituisce un numero positivo se e solo se $a \geq b$, come ci aspetteremmo. Se definiamo \binom{a}{a+1} = 0, questa formula tiene anche conto del caso $b=0$.

Non so scrivere i coefficienti binomiali.

Grazie per la risposta, molto ingegnosa, non ci sarei mai arrivato da solo.
Per la seconda parte avevo provato a scrivere la formula della probabilità di attraversare il fiume come probabilità di arrivare ad ogni punto "di frontiera" (ossia sulla retta $r: y=x$) moltiplicata per $q$, ossia la probabilità di dirigersi un'altra volta a nord.
La formula era dunque
$\sum_{i=0}^{n} C(i)p^(i)q^(i+1)$
Dove $C(i)$ sta per il numero di percorsi validi secondo le condizioni del problema per giungere all'i-esimo punto dalle coordinate intere della retta $y=x$, che è noto e corrisponde all'i-esimo numero di Catalan (che è ovviamente calcolabile anche con la formula da te trovata).
La tesi da dimostrare è dunque:
$q/p>=q\sum_{i=0}^{n} C(i)(pq)^(i)$
Che semplificando diventa:
$1/p>=\sum_{i=0}^{n} C(i)(pq)^(i)$
Da qui, sempre ammesso che il mio ragionamento finora è giusto, non saprei come continuare. Il massimo valore del membro a destra si può calcolare, e si ha quando $p=q=1/2$ perché si tratta di massimizzare un prodotto di fattori dalla somma fissata. Credo che la sommatoria sia possibile troncarla dopo i primi termini dato che gli addendi tendono rapidamente a zero perché $p$ e $q$ sono compresi tra $]0;1[$, ma non mi sembra un passaggio molto rigoroso.
Qualcuno ha delle idee o dei suggerimenti? Questo problema mi sta facendo impazzire, penso di aver sbagliato completamente approccio.

[axpgn]

Qui qualcosa di simile ...

[Vincent46]

Per il secondo punto, ci ho provato un pochino, ma non ho ottenuto nulla. Ho provato a esplicitare il numero di catalan e fare due conti, ma non mi usciva nulla di buono. Ad ogni modo volevo soltanto sottolineare che l'idea per il mio tentativo di soluzione l'ho presa pari pari dalla dimostrazione del valore dell'$n$esimo numero di catalan. La trovi qui alla voce "second proof":

https://en.wikipedia.org/wiki/Catalan_number

[consec]

Beh, allora immagino che sia un po' anche colpa mia che mi ostino a consultare le voci di Wikipedia in italiano ero convinto che quella dimostrazione valesse solo per i punti tali che $a=b$
Per il secondo punto dopo molta fatica dovrei aver abbozzato una soluzione, ragionando in maniera del tutto diversa rispetto al precedente post, anche se non so se quella strada fosse completamente da buttare.

Sia $Pr_(fiume)(p,q,n)$ la probabilità di attraversare il fiume almeno una volta, $Pr_(n-fiume)(p,q,n)$ la probabilità di non attraversare il fiume, dove $p$ è la probabilità di svoltare a est, $q$ la probabilità di svoltare a nord e $n$ il numero di incroci visitati, corrispondente alla somma $a+b$ del generico punto d'arrivo $P(a;b)$.
Fissato un $n$ qualsiasi, i traguardi possibili sono della forma $P(a;n-a)$, con $a$ che può assumere tutti i valori interi da $0$ a $n$.
Dal precedente punto, sappiamo che il numero totale di percorsi senza restrizioni è uguale a $((a+b),(a))$, il numero di percorsi che implicano l'attraversamento del fiume è uguale a $((a+b),(a+1))$ e il numero di percorsi che soddisfano le condizioni del problema è uguale a $((a+b),(a))-((a+b),(a+1))$.
Notiamo che per raggiungere tutti i punti della forma $P(a;n-a)$ con $a=n/2$ dovremo considerare solo i percorsi che abbiamo scartato nel punto precedente. La probabilità è data dalla somma dei singoli eventi indipenti moltiplicati per $p^a$ e $q^(n-a)$. Dunque

$Pr_(fiume)= \sum_{j=0}^{i=n/2-1}((n),(j))p^jq^(n-j) + \sum_{i=n/2}^{n}((n),(i+1))p^iq^(n-i)$

Ragionando in maniera analoga, stavolta considerando solo i cammini ammissibili per il primo punto

$Pr_(n-fiume)= \sum_{i=n/2}^{n}[((n),(i))-((n),(i+1))]p^iq^(n-i)$

Poiché, ovviamente, gli eventi "Alessia attraversa il fiume almeno una volta" e "Alessia non attraversa mai il fiume" esauriscono tutte le possibilità, la somma delle loro probabilità vale 1 (come tra l'altro si può notare sommando algebricamente le due formule, completando così lo sviluppo binomiale di $(p+q)^n$, che è uguale a 1 per le ipotesi del problema). Dunque

$Pr_(fiume)=1-Pr_(n-fiume)$

EDIT: Da qui in poi è sbagliato

Il secondo membro delle uguaglianza può essere scritto, spezzando le sommatorie e moltiplicando e dividendo la seconda sommatoria per q/p, come

$1-\sum_{i=n/2}^{n}((n),(i))p^iq^(n-i) + (q/p)*\sum_{i=n/2}^{n}((n),(i+1))p^(i+1)q^(n-(i+1))$

Notiamo che entrambe le sommatorie sono uguali a sviluppi parziali dello sviluppo binomiale di $(p+q)^n=1^n=1$, quindi sono minori o uguali a 1, e l'uguaglianza sussiste solo quando $q=0$ e $p=1$.
La precedente relazione è dunque $<= 1-[1-(q/p)*(1)]$, e la tesi risulta dimostrata.

[Vincent46]

ma nell'ultimo passaggio, quando maggiori la sommatoria che ha il segno $-$ davanti, dovresti eventualmente maggiorarla con il suo valore minimo, non puoi metterci il suo valore massimo.

[consec]

"Vincent46":

ma nell'ultimo passaggio, quando maggiori la sommatoria che ha il segno $-$ davanti, dovresti eventualmente maggiorarla con il suo valore minimo, non puoi metterci il suo valore massimo.

Hai ragione. Riflettendoci meglio mi viene così: la probabilità $Pr_(fiume)$ e $Pr_(n-fiume)$ hanno somma fissata, quindi al massimo di una corrisponde il minimo dell'altra.

$MAX(Pr_(n-fiume)) + MIN(Pr_(fiume)) = 1$

Il massimo di $Pr_(n-fiume)$ l'ho calcolato prima ed è uguale a $1-q/p$, quindi

$(1-q/p) + MIN(Pr_(fiume)) = 1$

Quindi
$MIN(Pr_(fiume)) = 1-(1-q/p)$ ossia

$Pr_(fiume) >= q/p$

Avrò sbagliato qualcosa nei segni, non so.

EDIT: Ripensandoci il max della probabilità di attraversare il fiume è sbagliato, dato che ho sostituito il massimo a entrambe le sommatorie nonostante sia una sottrazione. Credo che la soluzione del secondo punto fino alle formule della probabilità sia corretta, però.