This week’s Riddler Classic is a seasonal puzzle about leaves changing color.
The trees change color in a rather particular way. Each tree independently begins changing color at a random time between the autumnal equinox and the winter solstice. Then, at a random later time for each tree — between when that tree’s leaves began changing color and the winter solstice — the leaves of that tree will all fall off at once. At a certain time of year, the fraction of trees with changing leaves will peak. What is this maximal fraction?
My solution:
[Show Solution]
To simplify the problem a bit, suppose the autumnal equinox is at time $t=0$ and the winter solstice is at time $t=1$. Pick a tree, and let $u \in [0,1]$ be the time when the color begins to change, and $v \in [u,1]$ the time when the leaves fall from the tree. Since $u$ and $v$ are uniformly distributed, the joint distribution of $(u,v)$ needs to be scaled by $\frac{1}{1-u}$ so that it integrates to $1$. We can check that this works:
\[
\int_{u=0}^1 \int_{v=u}^1 \frac{1}{1-u}\,\mathrm{d}v\,\mathrm{d}u = 1
\]We are interested in the probability that the tree still has its leaves at time $x$. In other words, the probability that $u \leq x \leq v$. All we have to do is evaluate the same integral, but restrict ourselves to the points for which $u \leq x$ and $x \leq v$. In other words, the density function we seek is:
\begin{align}
f(x) &= \int_{u=0}^x \int_{v=x}^1 \frac{1}{1-u}\,\mathrm{d}v\,\mathrm{d}u
= \int_{u=0}^x \frac{1-x}{1-u} \,\mathrm{d}u
= -(1-x)\log(1-x)
\end{align}Here is a plot of this function.
We can find the maximum by taking the derivative and setting it equal to zero. The derivative is
\[
\frac{\mathrm{d}}{\mathrm{d}x}(x-1)\log(1-x)
= 1+\log(1-x)
\]and setting this equal to zero yields $x = 1-\frac{1}{e}\approx 0.63211$. The corresponding probability $f(x)$ is therefore:
$\displaystyle
f_\text{max} = \frac{1}{e} \approx 0.367879 = 36.8\%
$
Another way to solve the problem, courtesy of Matthew Wallace:
[Show Solution]
We can approach the problem using a differential equation model. Since trees change color at a uniformly distributed time, the rate of trees changing is constant throughout the time window. Similarly, given a fixed population of trees in bloom, we expect leaves to fall linearly with the number in bloom and inversely with the time left until the end of fall. To simplify, fix the time window to $[0,1]$ where $0$ is the start of fall and $1$ the end. Also, let the population of trees be non-dimensionalized so that $x=1$ would mean all the trees are in bloom and $x=0$ would mean none are. We then have the differential equation:
\[
\frac{\mathrm{d}x}{\mathrm{d}t} = 1-\frac{x}{1-t},\qquad x(0)=0
\]This is an ordinary differential equation and it can be solved using integrating factors. After some algebra, we obtain the solution
\[
x(t) =-(1-x)\log(1-x),
\]which is the same solution we obtained using the other approach!