Movie Tickets

Define $X_t$ to be the number of the first $t$ people in the queue who have $5; and define $Y_t=X_t-(t-X_t)$ the difference between this number and the number of the first $t$ people who do not have $5. Then we need (i) $Y_t>=0$ for all $t=1,2,..,10$ , and (ii) the first of the people without the $5 to have a $10 bill.

So if we can count the number, $N$ , of orders of the people with/without a $5 bill that satisfy (i), then for each of these there are 4 places for the person with $20 that satisfy (ii), so the answer is $4N$ .

Now to find $N$ we can use the reflection principle for a simple random walk. The number of orderings of the people is 10-choose-5 (we have 10 people, 5 with $5 bills). The number of these orderings that do not satisfy $Y_t>=0$ for all $t=1,..,10$ is just the number of ways of moving from $Y_0=-2$ to $Y_{10}=0$ as there is a 1-to-1 mapping between the paths from $Y_0=0$ to $Y_{10}=0$ that hit the value $-1$ and that paths $Y_0=-2$ to $Y_{10}=0$ *. This is 10-choose-6.

So $N$ is the difference of these: 10-choose-5 minus 10-choose-6; which is 42.

Hence the answer is 4 times 42, i.e. 168.

[*This mapping is obtained by reflecting the paths between time 0 and the time they first hit -1 about the line $y=-1$ .]

Let us first analise the queue replacing the person with the $\$20$ bill by a $\$10$ bill.

Now consider the following queue: $FFT \;F\; TFFTTT$ where F represents a person with a $\$5$ bill and T a $\$10$ dollar bill. From left to right, the above is a "good" queue, because the box office will always have change. Now, if we take, for example, the fourth person in the queue above and change all the people behind her with the people in front of her, in the same order, we get: $TFFTTT \;F\; FFT,$ wich is a "bad" queue. If we do that for each letter F for each "good" queue we get a "bad" one, and since all "good" and "bad" queues formed with this process are differente from one another, there are 5 "bad" queues for each "good" queue.

The total number , $x$ , of possible queues is given by $\binom{10}{5}$ . So $x = 252$ . The number of "good" queues is given by $N = \frac{x}{6} = 42$ .

Now we just have to replace one $\$10$ bill by a $\$20$ bill. There are 5 people with a $\$10$ dollar bill, but only the last four in the queue can be replaced, so there is change available. So, our final answer is $42\times4 = \boxed{168}.$

The number of configuration that satisfy the above conditions is equal to $4 \times C_{5}$ where $C_{n}$ represents the $n^{th}$ Catalan Number.

We know that $C_{5}$ = 42. Therefore the number of ways to arrange them in such a way that they satisfy the above condition is $4 \times C_{5} = \boxed{168}$ ways.