## Friday, October 16, 2009

### Show and Change

Credit for this problem goes to a friend of Boon Leong Ng.

A ticket to a show costs 10 dollars. There are $(m+n)$ (where $m > n$) people waiting on a line. $m$ of them pays with 10 dollar bills and $n$ of them pays with 20 dollar bills. Assuming that the cashier starts out with no money, what is the probability that the cashier never runs out of change? Assuming the probability is uniform among all possible ordering of people.

#### First Solution

The answer is $\frac{m-n+1}{m+1}$.

Before reading further into this solution, please read the boy and girl table here (including the harder version): http://dharmath.thehendrata.com/2009/10/22/boys-and-girls-around-the-table/

Now, suppose that the cashier secretly buys one ticket for herself by putting a 10 dollar bill in the box. She does this before serving the first person in line. We define that the cashier is "empty" if she has exhausted all the 10 bills that she has (including that first bill). Now the problem condition translates to: what is the probability that the cashier never becomes empty. That is, there is at least one 10 dollar bill in the box at all times.

For a given line configuration, let those people sit in a circle clockwise. The cashier, followed by the first person to her left, second person to his left, and so on, until the last person to the right of the cashier. Let the cashier and people who would pay 10 dollar bills become boys, and let people who would pay 20 dollar bills become girls. Make them play the stone game as described in the link above.

Say the cashier starts the game, representing her buying ticket for herself. The first person's turn in the stone game represents that person being served in the line, and so on. Note that the number of stones on the table corresponds exactly to the number of 10 dollar bills in the cashier box.

If the boys and girls could complete the whole round successfully, that means the cashier also succeeds at serving people without ever becoming empty. In other words, as long as the cashier is one of the boys who could start a non-losing game in the stone game. In a game with $m+1$ boys and $n$ girls, there are exactly $m+1-n$ such starter boys.

To sum up, once we are given a random line configuration, we form a circular configuration and perform the game, starting with the cashier. We want to know that the probability of that game to complete successfully. Since there are $m+1$ boys but only $m+1-n$ of them could start a non-losing game, the probability is $\frac{m-n+1}{m+1}$

#### Second solution

Suppose that there are two showings, Monday and Tuesday, and that today is Monday. There are $\binom{m+n}{m} = \frac{(m+n)!}{m!n!}$ ways of people to line up, and we wish to know how many ways would cause the cashier to never run out of change.

Suppose that the cashier DOES run out of change at some point, let her borrow 10 dollar bills from the stash and proceed with the line as usual. At the end of the line, she certainly has enough 10 dollar bills to return to the stash (because $m \geq n$). Suppose the first person who gets this borrowed money is called Andy.

Say on Tuesday, all these people come back and stand in exact same order. Everyone from the first person up to (including) Andy pays the same way as they did on Monday (10 dollar or 20 dollar bills). But everyone after Andy flips the bills that they paid with (10 dollar becomes 20 dollar and vice versa). We wish to know how many people now pay with which bills.

Because Andy is the first person who receives a borrowed money as a change, then everyone in front of him are split evenly between those who pay with 10 or with 20. Say there are $k$ of each. Andy himself must have paid and still pays 10. And then there were $m-k$ behind him who paid with 10, and $n-k-1$ behind him who paid with 20. On Tuesday, these people are flipped, so that now in total, there are $n-1$ who paid with 10 and $m+1$ who paid with 20 (including Andy).

Of course, because $m \geq n$, then $m+1 > n-1$. So on Tuesday, the cashier WILL run out of change for sure, but worry not, she can still borrow money from the stash and proceed normally with the line.

Now we have established a bijection between the line configurations on Monday where she runs out of change and all the possible configurations on Tuesday. We just described how to obtain a Tuesday configuration from Monday (by flipping everyone's payment after Andy). But say we are given a line configuration on Tuesday, we can correctly identify the corresponding line on Monday by first identifying Andy. On Tuesday, the cashier is guaranteed to run out of change. The first person that is paid with borrowed money on Tuesday is Andy. We then take the remainder of the line and flip their payment to get Monday's line.

Thus, the number of configurations on Monday where she runs out of change is the same as total possible configurations on Tuesday, that is $\binom{m+n}{n-1}$.

So the number of configurations on Monday where she does NOT run out of change is $\binom{m+n}{m} - \binom{m+n}{n-1} = \frac{m-n+1}{m+1} \binom{m+n}{m}$, so that the probability is $\frac{m-n+1}{m+1}$

#### Third solution

We define that the cashier is "empty" if she has exhausted all the 10 bills that she has. For example, if the first person pays with 10 and second person with 20, then the cashier is empty after the second person. Note that emptiness does not mean she runs out of change. It depends on the third person.

Let $f(m,n)$ be the number of configurations where she never runs out of change (we will call admissible configurations).

Consider the first time the cashier becomes empty. This condition must happen after an even number of people, say after $k$ people who paid with 10 and $k$ people who paid with $20$. We wish to see how many configurations there are such that the cashier becomes empty the first time precisely after the first $2k$ people.

The first person in line must pay with 10, and the $2k$-th person must pay with 20 for it to happen. Then, person $2,3,\cdots, 2k-1$ can be in any configuration they want as long as it does not make the cashier empty. There are $f(k-1,k-1)$ ways to do so. Imagine that the first 10 that she gets is reserved for that $2k$-th person and person $2,\cdots,2k-1$ can be in any admissible configuration and the cashier would not be empty.

But what about the rest of the people? The cashier may become empty again or not, doesn't matter, as long as the rest of the configuration is admissible. From $2k+1$ to $m+n$, it's as if the cashier started anew. So there are $f(m-k, n-k)$ ways to do so.

So there are $f(k-1,k-1) f(m-k,n-k)$ ways people could line up such that the cashier becomes empty the first time after $2k$ people. Note that $k$ can range from 1 to $n$.

What about the case where the cashier never becomes empty at all? There are $f(m-1,n)$ such configurations. Imagine that the cashier saves the first person's 10 bill in a special drawer and pretends that she starts anew starting with the second person. The rest of people can have any admissible configuration and the cashier would never become empty.

Now, our recursive formula then is:

$f(m,n) = \sum_{k=1}^{n} f(k-1,k-1) f(m-k,n-k) + f(m-1,n)$

The solution for this recursive formula is described here: http://dharmath.thehendrata.com/2009/10/23/2-variable-recursion/

The number of configurations is $f(m,n) = \frac{m-n+1}{m+1} \binom{m+n}{m}$, while the total number of configuration is $\binom{m+n}{m}$. Thus, the probability the cashier never runs out of change is $\frac{m-n+1}{m+1}$

#### Fourth Solution

1. alternate approach using probability:

P(has change)
= P(m,n)
= P(has change given last person is from m) * P(last from m) + (has change given last person is from n) * P(last from n)
= P(m-1, n) * m/(m+n) + P(m, n-1)* n/(m+n)

where P(last from m) = m/(m+n) because we can pick any one of them to be at the end. Similarly for P(last from n).

Now, we know that P(m, 0) = 1 for any positive integer m. Also, we define P(m, n) = 0 for m = 1. (however note that m and n must be nonnegative as assumed in our recursion)

2. We proceed by induction on k, where k = m+n. Assume that the conjecture is true for k-1.

P(m,n)
= P(m-1,n) * m/(m+n) + P(m,n-1) * n/(m+n)
= [(m-n)/m] * [m/(m+n)] + [(m-n+2)/(m+1) * n/(m+n)]
= [(m-n)(m+1) + n(m-n+2)]/[(m+1)(m+n)]
= (m^2+m-mn-n+mn-n^2+2n)/[(m+1)(m+n)]
= (m62+m+n-n^2)/[(m+1)(m+n)]
= [(m+n)(m-n) + (m+n)]/[(m+1)(m+n)]
= (m-n+1)/(m+1)

so the induction hypothesis holds for k.
For k = 1 consider:
P(1,0) = (1-0+1)/2 = 1 as expected
P(0,1) = (0-1+1)/1 = 0 as expected

Hence by induction the hypothesis is true for positive integers k >= 1. (however note that m and n must be nonnegative as assumed in our recursion)

Also, we define P(m, n) = 0 for m < n

Calculating using python script:
P(1,1) = 1/2
P(2,1) = 2/3
P(3,1) = 3/4
... conj: P(m,1) = m/(m+1)

P(2,2) = 1/3
P(3,2) = 2/4
P(4,2) = 3/5
... conj: P(m,2) = (m-1)/(m+1)

P(3,3) = 1/4
P(4,3) = 2/5
P(5,3) = 3/6
... conj: P(m,3) = (m-2)/(m+1)

Hence, we conjecture that P(m,n) = (m-n+1)/(m+1)