Kasa Teatralna

[janusz47]

Na forum pojawiło się ciekawe zadanie z rachunku prawdopodobieństwa, które z powodu niestosowania zapisu w LateX, znalazło się w koszu.

Oto jego treść:
W kolejce do kasy teatralnej stoi \(\displaystyle{ 2n}\) osób; \(\displaystyle{ n}\) osób na tylko banknoty o wartości \(\displaystyle{ 20}\) złotych, a pozostałe \(\displaystyle{ n}\) osób - tylko o wartości \(\displaystyle{ 10}\) złotych. Na początku sprzedaży w kasie nie ma pieniędzy. Każda osoba kupuje jeden bilet o wartości \(\displaystyle{ 10}\) złotych. Jakie jest prawdopodobieństwo tego, że żadna osoba nie będzie czekać na resztę?

Rozwiązanie

Kupowanie biletów na do teatru można zobrazować w układzie współrzędnych kartezjańskich w postaci linii łamanej, oznaczając osoby kupujące bilety przez \(\displaystyle{ O_{1}, O_{2}, ..., O_{2n-1}, O_{2n}}\)

Jeśli osoba np. \(\displaystyle{ O_{1}}\) kupuje bilet za \(\displaystyle{ 10}\) zł przyporządkowujemy jej punkt \(\displaystyle{ (1, 1)}\) jeśli zaś kupuje bilet za \(\displaystyle{ 10}\) zł a daje \(\displaystyle{ 20}\) zł wtedy - przyporządkowujemy jej punkt o współrzędnych \(\displaystyle{ (-1, -1).}\)

Zakładamy, że osobie \(\displaystyle{ O_{k}}\) przyporządkowany jest punkt o współrzędnych \(\displaystyle{ O_{k} (k, y_{k}), \ \ k=1,2,3,..., 2n-1,}\) przy czym \(\displaystyle{ y_{k}=1,}\)lub \(\displaystyle{ y_{k} =-1.}\)

Punkt \(\displaystyle{ O_{k+1}}\) na linii łamanej jest połączony z punktem \(\displaystyle{ O_{k},}\) przy czym jeżeli, osoba \(\displaystyle{ k+1}\) daje \(\displaystyle{ 10}\) zł, wtedy rzędna \(\displaystyle{ y_{k+1}= y_{k}+1}\) w przeciwnym przypadku \(\displaystyle{ y_{k+1} = y_{k}-1.}\)

Ostatni punkt linii łamanej \(\displaystyle{ O_{2n} =( 2n, y_{2n}),}\) gdzie \(\displaystyle{ y_{2n}= 0}\) ponieważ \(\displaystyle{ n}\) osób daje \(\displaystyle{ 10}\) i \(\displaystyle{ n}\) osób \(\displaystyle{ 20}\) zł.

Łamana składa się z odcinków \(\displaystyle{ O_{k}O_{k+1}, \ \ k=1,2,..., (2n-1), 2n}\) Ostanie jej punkty \(\displaystyle{ O_{2n}}\) i \(\displaystyle{ O'_{2n}}\) mogą być symetryczne względem prostej \(\displaystyle{ y = -1,}\) współrzędne punktu \(\displaystyle{ O'_{2n}= ( 2n, -2 )}\)

Mamy więc \(\displaystyle{ n+1}\) dolnych i \(\displaystyle{ n-1}\) górnych odcinków łamanej.

Stąd szukane prawdopodobieństwo

\(\displaystyle{ P = \frac{{2n \choose n}- {2n \choose n+1}}{{2n\choose n}}}\)

Różnica

\(\displaystyle{ {2n \choose n} - {2n \choose n+1}= {2n\choose n} - \frac{n}{n+1}{2n\choose n} = \frac{1}{n+1}{2n\choose n}.}\)

\(\displaystyle{ P = \frac{\frac{1}{n+1}{2n\choose n}}{{2n\choose n}} = \frac{1}{n+1}.}\)

W kombinatoryce liczby \(\displaystyle{ \frac{1}{n+1}{2n\choose n}}\) nazywamy liczbami Catalana.

[Tmkk]

Znając interpretację liczb Catalana, można to zrobić bardzo szybko.

Ustawmy ich jakoś i ponumerujmy osoby, które mają \(\displaystyle{ 20}\) zł po kolei przez \(\displaystyle{ 1,2,\ldots,n}\). Niech \(\displaystyle{ f : [n] \to [n]}\) będzie taka, że \(\displaystyle{ f(k) = l}\), jeśli przed osobą z numerkiem \(\displaystyle{ k}\), stoi \(\displaystyle{ l}\) osób z banknotami \(\displaystyle{ 10}\) zł. Funkcja ta jest niemalejąca.
Aby warunki zadania były spełnione musi być \(\displaystyle{ f(k)\ge k}\), czyli zdarzeń sprzyjających jest tyle, ile funkcji niemalejących o tym warunku. Czyli jest to po prostu \(\displaystyle{ n}\) - ta liczba Catalana.