Cashier has no change... catalan numbers.. probability question
I think this question uses catalan numbers.. but I don't know exactly how to answer it... its not homework or anything but I need to understand how to do it.. I tried drawing up likes for each 5r dolla bill the cashier has and down lines for each one he gave as change.. attempting to create "mountains" but the possibilities become very large extremely quickly which is giving me trouble creating an equation.. anyhow here is the question...
75 people have 5 dollar bills and 25 people have 10 dollar bills, and they are in line at a ticket counter which has no money and which charges 5 dollars for admission. If a 10 dollar bill is presented and there is no change, the line stops. What is the probability that the ticket seller always (after the first person in line, that is) has at least one 5 dollar bill for change?
As above, what is the probability the ticket seller was always able to make change.
What is the probability that the ticket seller was always able to make change if he is now allowed to use his own, single 5 dollar bill, if needed?
Solution 1:
Here's an answer to the first question. Since the other two questions are variations of the first one, they are left as challenge for you! :-)
Problem: We have $75$ people with $5$ dollar bills and $25$ people with $10$ dollar bills in line at a ticket counter which has no money and which charges $5$ dollars for admission. If a $10$ dollar bill is presented and there is no change, the line stops. What is the probability that the ticket seller always (after the first person in line, that is) has at least one $5$ dollar bill for change?
Analysis: We have queues of length $100$ with \begin{align*} \binom{75+25}{25}\tag{1} \end{align*} possible configuration. In order to get a valid configuration it has to be assured, that for each person with a $10$ dollar bill at least one other person with a $5$ bill has to be in front of him.
Lattice paths:
A nice way to describe the situation is using lattice paths. We consider paths of length $100$ starting at $A=(0,0)$ and ending at $B=(75,25)$. The paths consist of $(1,0)$-steps in $x$-direction representing persons with $5$ dollar bills and $(0,1)$-steps in $y$-direction representing persons with $10$ dollar bills. Since for each $10$ dollar bill a person with a $5$ dollar bill has to be in front, the valid paths are those having at each point a $y$-height less or equal the $x$-length.
We observe:
The number of all possible configurations is the number of all paths with length $100$ from $A=(0,0)$ to $B=(75,25)$.
The number of valid configurations is the number of paths with length $100$ from $(0,0)$ to $(75,25)$ which do not touch the line $y=x+1$.
The number of pathes from $(0,0)$ to $(75,25)$ with length $100$ is according to (1): $\binom{100}{25}$ since we can select $25$ $(0,1)$-steps in $y$-direction out of $100$ leaving $75$ left for the $(1,0)$-steps in $x$-direction.
Andre's Reflection Principle: The number of invalid configurations can be calculated using Andre's reflection principle. A path is invalid if it touches or crosses the line $y=x+1$. In any case it touches the line the first time at let's say $P$. Now, we reflect the first part of the path from $A=(0,0)$ to $P$ at the line $y=x+1$ getting a path from $A^\prime=(-1,1)$ via $P$ to $B=(75,25)$. The second part of the path from $P$ to $B$ is the same as the original path.
We observe: Each invalid path from $A=(0,0)$ to $B=(75,25)$ has to touch at least once the line $y=x+1$ and corresponds bijectively to the reflected path $A^\prime=(-1,1)$ via $P$ to $B$, whereby the second part of the path from $P$ to $B$ is identical to the original path.
Since this is a bijection we conclude: The number of invalid paths from $A$ to $B$ is the number of all paths from $A^\prime$ to $B$, namely:
\begin{align*} \binom{76+24}{24} \end{align*}
Result:
The resulting probability is the number of valid paths divided by the number of all paths:
\begin{align*} \frac{\binom{100}{25}-\binom{100}{24}}{\binom{100}{25}}=\frac{51}{76}\approx 0.671 \end{align*}
Note: This problem is a variation of Bertrand's ballot theorem. The relationship with the Catalan Numbers $\frac{1}{n+1}\binom{2n}{n}$ is stated there in the section equivalent problems in this page.