HMMT-Feb 2012 guts, Problem 30

You have a twig of length 1. You repeatedly do the following: select two points on the twig independently and uniformly at random, make cuts on these two points, and keep only the largest piece. After 2012 repetitions, what is the expected length of the remaining piece?

Solution: First let $p(x)$ be the probability density of $x$ being the longest length. Let $a_{n}$ be the expected length after $n$ cuts. $a_{n}=\int_{0}^{1} p(x) \cdot\left(x a_{n-1}\right) d x=a_{n-1} \int_{0}^{1} x p(x) d x=a_{1} a_{n-1}$. It follows that $a_{n}=a_{1}^{n}$, so our answer is $\left(a_{1}\right)^{2012}$. We now calculate $a_{1}$. Let $P(z)$ be the probability that the longest section is $\leq z$. Clearly $P(z)=0$ for $z \leq \frac{1}{3}$. To simulate making two cuts we pick two random numbers $x, y$ from $[0,1]$, and assume without loss of generality that $x \leq y$. Then picking two such points is equivalent to picking a point in the top left triangle half of the unit square. This figure has area $\frac{1}{2}$ so our $P(z)$ will be double the area where $x \leq z, y \geq 1-z$ and $y-x \leq z$. For $\frac{1}{3} \leq z \leq \frac{1}{2}$ the probability is double the area bounded by $x=z, 1-z=y, y-x=z$. This is $2\left(\frac{1}{2}(3 z-1)^{2}\right)=(3 z-1)^{2}$. For $\frac{1}{2} \leq z \leq 1$ this value is double the hexagon bounded by $x=0, y=1-z, y=x, x=z, y=1$, $y=x+z$. The complement of this set, however, is three triangles of area $\frac{(1-z)^{2}}{2}$, so $P(z)=1-3(1-z)^{2}$ for $\frac{1}{2} \leq z \leq 1$. Now note that $P^{\prime}(z)=p(z)$. Therefore by integration by parts $a_{1}=\int_{0}^{1} z p(z) d z=\int_{0}^{1} z P^{\prime}(z) d z=$ $\left[{ }_{0}^{1} z P(z)-\int_{0}^{1} P(z) d z\right.$. This equals \[ \begin{aligned} & 1-\int_{\frac{1}{3}}^{\frac{1}{2}}(3 z-1)^{2} d z-\int_{\frac{1}{2}}^{1} 1-3(1-z)^{2} d z \end{aligned} \] \[ \begin{aligned} & =1-\frac{1}{72}-\frac{1}{2}+\frac{1}{8}=\frac{1}{2}+\frac{1}{9} \\ & =\frac{11}{18} \end{aligned} \] So the answer is $\left(\frac{11}{18}\right)^{2012}$. $\fbox{(11 / 18)^{2012}}$.

Answer: (11 / 18)^{2012}