[Math] Ticket-Change probability problem

combinatoricsprobabilitystatistics

Here is another question from the book of V. Rohatgi and A. Saleh. I would like to ask help again. Here it goes:

Waiting in line for a Saturday morning movie show are $2n$ children. Tickets are priced at a quarter each. Find the probability that nobody will have to wait for change if before a ticket is sold to the first customer, the cashier has $2k$ ($k<n$) quarters. Assume that it is equally likely that each ticket is paid for with a quarter or a half-dollar coin.

I find it hard to understand the phrase "nobody waits for change". I hope someone can help. Thanks.

Best Answer

Hint: Apply the reflection principle in a similar way to deal with the general case.

This problem is equivalent to starting at $(0, 2k)$ with steps of $(1,1)$ and $(1, -1)$. Without restriction, there are $2^{2n}$ possible paths.

How many ways are there which do not go below the line $y=0$? That's the number of ways that do not touch the line $y=-1$. Let's count the complement, namely the number of lines which touch $y=-1$.

For each such path, using the reflection principle, we reflect the path after the last point of contact with the line $y=-1$. This gives us a path from $(0, 2k)$ which ends with $y \leq -1$. Now show that this is a bijection.

The number of such paths is thus clearly $\sum_{i=0}^j { 2n \choose i}$ for a certain value of $j$ which you should determine.

Let's say we took $a$ up steps and $2n-a$ down steps. Since we started out at $(0,2k)$, we would end up at a y-coordinate of $2k + a - (2n-a) = 2k+2a - 2n$. We want this to be $\leq -1$, and hence $2a \leq 2n - 2k - 1 \Rightarrow a \leq n - k - 1$ (since they are all integers). This is our value of $j$.

Related Question