# Solution to puzzle 53: The absentminded professor

An absentminded professor buys two boxes of matches and puts them in his pocket. Every time he needs a match, he selects at random (with equal probability) from one or other of the boxes. One day the professor opens a matchbox and finds that it is empty. (He must have absentmindedly put the empty box back in his pocket when he took the last match from it.) If each box originally contained `n` matches, what is the probability that the other box currently contains `k` matches? (Where 0 k n.)

If k matches remain in the other box, then n−k matches have been selected from that box.

Suppose the professor attempts to select the (n+1)st match from the box in his *left* pocket.

Then a total of 2n−k+1 selections have been made; thus we have 2^{2n−k+1} ways in which the matches can be selected.

Of these, _{2n−k}C_{n} (where _{m}C_{r} = m! / [r! (m−r)!] is the number of ways of choosing r outcomes out of m possibilities, ignoring order) combinations are such that the (n+1)st selection is from his left pocket.

Therefore the probability the professor will open an empty box from his left pocket is _{2n−k}C_{n} / 2^{2n−k+1}.

Of course, there is an equal probability that he will open an empty box from his right pocket.

Therefore the probability that the other box currently contains k matches is _{2n−k}C_{n} / 2^{2n−k}.

## Remarks

Let p_{n}(k) denote the probability that the other box currently contains k matches.

We have p_{n}(k) | = _{2n−k}C_{n} / 2^{2n−k}. |

| = (2n−k)! / [n! (n−k)! 2^{2n−k}]. |

Then p_{n}(k+1) / p_{n}(k) | = [(2n−k−1)! (n−k)! 2^{2n−k}] / [(2n−k)! (n−k−1)! 2^{2n−k−1}]. |

| = (2n − 2k) / (2n − k). |

Hence p_{n}(0) = p_{n}(1), and p_{n}(k+1) < p_{n}(k), for k > 0.

The histogram below shows the probability, p_{50}(k), of the other box containing k matches, given that both boxes initially have 50 matches. For k > 25, p_{50}(k) < 1/1000. The expected value of p_{50}(k) 7.0385.

## Further reading

This puzzle is known as Banach's Matchbox Problem, after Stefan Banach, a Polish mathematician of the early twentieth century. Banach did much work in functional analysis, and was co-discoverer of the Banach-Tarski paradox.

For a Java simulation, see Banach Matchbox Applet, from the page Welcome to Probability by Surprise.

Source: Stefan Banach

Back to top