Probability Problem Involving e I thought of the following probability problem, which seems to have an answer of 1/e, and wonder if someone has an idea as to how to prove this.
Suppose a man has a bottle of vitamin pills and wishes to take a half pill per day.  He selects a pill from the bottle at random.  If it is a whole pill he cuts it in half, takes a half pill, and puts the other half back in the bottle.  If it is a half pill, he takes that.  He continues this process until the bottle is empty.  What is the expected maximum number of half pills in the bottle?  If the bottle starts with n pills, and M is the expected maximum number of half pills, then M/n appears to tend to 1/e as n tends to infinity. 
 A: One way of solving the problem (probably not the easiest) is via the "differential equation method" (see eg the paper by Nick Wormald, entitled "The differential equation method for random graph processes and greedy algorithms", in Lectures on Approximation and Randomized Algorithms, pp. 73-155).
Suppose there are $n$ pills in the beginning. Let
$$
P(\lceil tn\rceil) = \text{number of whole pills after $\lceil tn\rceil$ steps}
$$
and 
$$
H(\lceil tn\rceil) = \text{number of half pills after $\lceil tn\rceil$ steps}
$$
Clearly, $2P(\lceil tn\rceil) + H(tn) = 2n - \lceil tn\rceil$.
Moreover, let $p(t) = \frac1{n}P(\lceil tn\rceil)$, and define $h(t)$ similarly.
Now, given the state $S_{\lceil tn\rceil}$ of the system after $\lceil tn\rceil$ steps, observe that
$$
\mathbb{E}[P(\lceil tn\rceil+ 1)  ~|~ S_{\lceil tn\rceil}] = P(\lceil tn\rceil) - \frac{P(\lceil tn\rceil)}{P(\lceil tn\rceil) + H(\lceil tn\rceil)}.
$$
This suggests that, up to negligible error terms, $p(t)$ satisfies the ODE
$$
p'(t) = -\frac{p(t)}{p(t) + h(t)}
$$
with initial condition $p(0) = 1$. Similalry, $h(t)$ satisfies
$$
h'(t) = \frac{p(t)}{p(t) + h(t)}-\frac{h(t)}{p(t) + h(t)}
$$
and $h(0) = 0$. With this it shouldn't be too difficult to get the maximum of $h(t)$.
A: The problem is equivalent to the following: Suppose there are $n$ bins, and repeatedly, we throw balls which fall in one of the bins (uniformly and independently of the history). What is the maximum number of bins with exactly one ball? In the model with the pills, it is explicitly forbidden to draw a pill which has been drawn twice already, but for the current question, this clearly doesn't matter.
We can replace discrete time with continuous time, and throw the balls at the events of a Poisson process. This way, the balls falling in a particular bin arrive according to a Poisson process, and different bins are independent. If the problem was to determine the time $t$ to maximize the expected number of bins with exactly one ball at time $t$, then the answer would clearly be to choose $t$ so that the expected number of balls in a bin is 1, and the probability of having exactly one ball would be $1/e$ (we are maximizing $xe^{-x}$). 
By the law of large numbers, the number of bins with exactly one ball will very likely be about $n/e$ at that time. To conclude that $M/n$ converges to $1/e$ in probability, it only remains to show that "exceptional times" with unusually many bins of exactly one ball are not likely to occur. I guess this can be established by quantifying the idea that if at time $t$ there are substantially more than $n/e$ bins with exactly one ball, then most likely there will continue  to be so in a time interval after $t$, which is unlikely.  
