Pill puzzle

The pill jar puzzle is a probability puzzle, which asks the expected value of the number of half-pills remaining when the last whole pill is popped from a jar initially containing n whole pills and the way to proceed is by removing a pill from the bottle at random. If the pill removed is a whole pill, it is broken into two half pills. One half pill is consumed and the other one is returned to the jar. If the pill removed is a half pill, then it is simply consumed and nothing is returned to the jar.

Mathematical derivation

The problem becomes very easy to solve once a binary variable X_k defined as X_k = 1, if the kth half pill remains inside the jar after all the whole pills are removed. The kth half pill is defined as the result of the breaking of the kth whole pill being removed from the jar. X_k = 1 if out of the n − k + 1 pills (n − k whole pills + kth half pill), the one half pill is removed at the very end. This occurs with probability 1/(n − k + 1).

The expected value is then given by, E(X₁) + E(X₂) + ... + E(X_n). Since E(X_k) = P(X_k = 1) = 1/(n − k + 1), the sought expected value is 1/n + 1/(n − 1) + 1/(n − 2) + ... + 1 = H_n (the nth harmonic number).