A hot summer day

Keep track of the number of £1 coins I have. Every time I sell a drink, this number goes up by $1$ if the next customer has a £1 coin, and goes down by $1$ if the next customer has a £2 coin (unless I have no £1 coins left, and I cannot sell that customer a drink). If we plot the number of £1 coins against the number of customers served at any stage, we can represent a day's sales as a piecewise linear path in $\mathbb{R}^2$ , starting at $(0,0)$ and ending at $(m+n,m-n)$ , where each successive vertex is obtained from the previous vertex by adding either $\binom{1}{1}$ or $\binom{1}{-1}$ . As we move from $x=k$ to $x=k+1$ , we either step up by $1$ or step down by $1$ .

There are $\binom{m+n}{m}$ orders in which the customers can appear, each order being equally likely.

We want to know the number of customer orders that exist so that my stock of £1 coins never runs out, so we want paths from $(0,0)$ to $(m+n,m-n)$ which never hit the line $y=-1$ . We do this by counting the number of paths that do hit the line $y=-1$ .

If a path from $(0,0)$ to $(m+n,m-n)$ does hit the line $y=-1$ , there must be an earliest point $x=k$ on this path where the line $y=-1$ is reached. If we reflect the portion of the path from $x=0$ to $x=k$ in the line $y=-1$ , we obtain a path from $(0,-2)$ to $(m+n,m-n)$ that first crosses the line $y=-1$ at the point $x=k$ .

Conversely, if we consider a path from $(0,-2)$ to $(m+n,m-n)$ , then there must be a first point $x=k$ that crosses the line $y=-1$ . Reflecting the first portion of the path in the line $y=-1$ , we obtain a path from $(0,0)$ to $(m+n,m-n)$ that first meets the line $y=-1$ at the point $x=k$ .

Thus the number of paths from $(0,0)$ to $(m+n,m-n)$ that meet the line $y=-1$ is equal to the number of paths from $(0,-2)$ to $(m+n,m-n)$ . Since such a path will involve $m+1$ steps of $1$ and $n-1$ steps of $-1$ , we deduce that there are $\binom{m+n}{m+1}$ such paths. Thus the probability that I cannot serve all the customers is $\frac{\binom{m+n}{m+1}}{\binom{m+n}{m}} \; = \; \frac{n}{m+1}$ and so the probability that I can serve all the customers is $1 - \frac{n}{m+1} \; = \; \frac{m+1-n}{m+1} \hspace{2cm} m \ge n$ For $n=3$ we deduce that probability $\boxed{\frac{m-2}{m+1}}$ for all $m \ge 3$ .