HMMT-Feb 2014 guts, Problem 29

Natalie has a copy of the unit interval $[0,1]$ that is colored white. She also has a black marker, and she colors the interval in the following manner: at each step, she selects a value $x \in[0,1]$ uniformly at random, and (a) If $x \leq \frac{1}{2}$ she colors the interval $\left[x, x+\frac{1}{2}\right]$ with her marker. (b) If $x>\frac{1}{2}$ she colors the intervals $[x, 1]$ and $\left[0, x-\frac{1}{2}\right]$ with her marker. What is the expected value of the number of steps Natalie will need to color the entire interval black?

Solution: The first choice always wipes out half the interval. So we calculate the expected value of the amount of time needed to wipe out the other half. Solution 1 (non-calculus): We assume the interval has $2 n$ points and we start with the last $n$ colored black. We let $f(k)$ be the expected value of the number of turns we need if there are $k$ white points left. So we must calculate $f(n)$. We observe that \[ \begin{gathered} f(k)=1+\frac{(n-k+1) \cdot 0+(n-k+1) \cdot f(k)+2 \sum_{i=1}^{k-1} f(i)}{2 n} \\ f(k) \frac{n+k-1}{2 n}=1+\frac{\sum_{i=1}^{k-1} f(i)}{n} \\ f(k+1) \frac{n+k}{2 n}=1+\frac{\sum_{i=1}^{k} f(i)}{n} \\ f(k+1)=f(k) \frac{n+k+1}{n+k} \\ f(k)=f(1) \frac{n+k}{n+1} \end{gathered} \] And note that $f(1)=2$ so $f(n)=\frac{4 n}{n+1}$ and $\lim _{n \rightarrow \infty} f(n)=4$. Therefore adding the first turn, the expected value is 5 . Solution 2 (calculus): We let $f(x)$ be the expected value with length $x$ uncolored. Like above, $\lim _{x \rightarrow 0} f(x)=2$. Similarly we have the recursion \[ \begin{gathered} f(x)=1+\left(\frac{1}{2}-x\right) f(x)+2 \int_{0}^{x} f(y) d y \\ f^{\prime}(x)=0+\frac{1}{2} f^{\prime}(x)-f(x)-x f^{\prime}(x)+2 f(x) \\ \frac{f^{\prime}(x)}{f(x)}=\frac{1}{x+\frac{1}{2}} \end{gathered} \] And solving yields $f(x)=c\left(\frac{1}{2}+x\right)$ and since $\lim _{x \rightarrow 0} f(x)=2, c=4$. So $f(x)=2+4 x$ and $f\left(\frac{1}{2}\right)=4$. Therefore adding the first turn, our expected value is 5 . $\fbox{5}$.

Answer: 5