# 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 22n−k+1 ways in which the matches can be selected.
Of these, 2n−kCn (where mCr = 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−kCn / 22n−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−kCn / 22n−k.

## Remarks

Let pn(k) denote the probability that the other box currently contains k matches.

 We have pn(k) = 2n−kCn / 22n−k. = (2n−k)! / [n! (n−k)! 22n−k].
 Then pn(k+1) / pn(k) = [(2n−k−1)! (n−k)! 22n−k] / [(2n−k)! (n−k−1)! 22n−k−1]. = (2n − 2k) / (2n − k).

Hence pn(0) = pn(1), and pn(k+1) < pn(k), for k > 0.

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