[SNS 2014] La città di Sapi

[RichyZ99]

Nel test per l'anno accademico 2014/15 della Scuola Normale di Pisa ho trovato il seguente problema, che mi ha dato non pochi grattacapi:

La città di Sapi è una città immaginaria, di estensione infinita; copre l'intero piano cartesiano; le strade sono le rette orizzontali e verticali con equazione $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+ \frac{1}{2} .\]

Alessia si muove per la città senza mai fermarsi partendo dall'incrocio $(0,0)$ e procedendo solo verso nord o verso est.

[list=1]
[*:2cp5liza]Quanti sono i possibili percorsi che Alessia può effettuare per raggiungere l'incrocio di coordinate $(a,b)$ senza attraversare mai il fiume?[/*:m:2cp5liza]
[*:2cp5liza]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 $\frac{q}{p}$.[/*:m:2cp5liza][/list:o:2cp5liza]

Mentre in un “normale” reticolo $x \times y$ i percorsi distinti sono $\frac{(x+y)!}{x! \cdot y!}$, in questo caso il problema è complicato dal fatto che non tutti i nodi del reticolo sono accessibili: il punto $(2,2)$, ad esempio, può essere raggiunto solo in 2 modi differenti anziché i “soliti” 6.
Noto anche che i nodi subito sotto la retta rispecchiano i numeri di Catalan come numero di percorsi che vi arrivano. Ciò nonostante, non ho affatto idee su come generalizzare rispetto alle coordinate generiche $(a,b)$.

[orsoulx]

Benvenuto nel forunm Richy99, i numeri di percorsi diversi che collegano l'origine con il punto $ (a,b) $ è $ ((a+b),(b))-((a+b),(b-1)) $. Si può dimostrare per induzione sui valori della somma.
Ciao