Stefan Banach was one of the early 20th century’s most important mathematicians - if you’re at all interested in popular maths, you’ll have heard of the Banach-Tarski paradox; if you’ve done any serious linera algebra, you’ll know about Banach spaces; if you’ve read Cracking Mathematics (available wherever good books are sold), you’ll recognise his name from the chapter on the Scottish Cafe.

So obviously, I’ve picked a much less serious example from the list of things named after him: Banach’s matchbox problem. So far as I know, the problem is not due directly to Banach: how I imagine it got the name is that Steinhaus had a probability problem and wanted to tease Banach about how much he smoked. It’s not the problem that is Banach’s, but the matchbox.

Or rather, matchboxes.

### The problem

Professor Banach starts the day with a box of matches in each pocket, each containing $N$ matches. Throughout the day, he removes a match from either pocket at random. At some point, he reaches for a match and finds the box he’s picked is empty. What’s the probability that the other box has $k$ matches remaining?

It’s easy to work the cases out for small $N$. In the trivial case, when $N=0$, there are obviously always 0 matches in the other pocket.

When $N=1$, suppose he picks the left pocket first. If he picks the right pocket next (which he will do with probability $\frac{1}{2}$), he will find the other matchbox has no matches left; if he picks left, he’ll find the other matchbox has one match. 0 and 1 are equally likely answers.

How about $N=2$? That’s more complicated. Again, suppose he picks left first. This time, working it through, the probabilities are $\frac{1}{4}$ for $N=2$ and $\frac{3}{8}$ for $N=1$ and for $N=0$.

### The general case

If Professor Banach finds $k$ matches remaining in the left matchbox after exhausting the right, he must have picked the left pocket $N-k$ times and the right pocket $N$ times, before finally picking the right pocket.

Those first $2N-k$ choices can be ordered $\nCr {2N-k}{N-k}$ ways; each way has a probability of $\br{\frac{1}{2}}^{2N-k}$ of occurring. We need to take into account the final choice (with probability of a half) but also that we’d get the same result using the other pocket (so we need to double our probability).

Overall, if $X$ is the random variable describing the number of left-over matches, we have $P(X=k) = \nCr{2N-k}{N-k} \br{\frac{1}{2}}^{2N-k}$.

* Edited 2019-02-09 to change category