A worm is called an adult if its length is one meter. In one operation, it is possible to cut an adult worm into two (possibly unequal) parts, each of which immediately becomes a worm and begins to grow at a speed of one meter per hour and stops growing once it reaches one meter in length. What is the smallest amount of time in which it is possible to get $n{}$ adult worms starting with one adult worm? Note that it is possible to cut several adult worms at the same time.
Problem
Source: Russian TST 2015, Day 7 P1
Tags: combinatorics
starchan
07.05.2023 14:24
solved with M.V.Adhitya and mueller.25
Suppose $f(n)$ is the minimum time it takes to get $n$ adult worms starting with one adult worm. Observe that $f(1) = 0$. Suppose we cut the initial worm into smaller worms of size $x$ and $1-x$, where $x \in (0, 1)$. If the $x$ length worm, after maturing grows into exactly $k$ worms; then the other one must grow into at least $n-k$ worms, implying that $f(n) \geq \min_{1 \leq k < n, x \in (0, 1)} \max(1-x+f(k), x+f(n-k))$. Fixing some $k$, the optimum value of $x$ is obviously when the two quantities involved are equal; hence $f(n) \geq \min_{1 \leq k \leq n} \frac{1+f(k)+f(n-k)}{2}$. It is easy to see that this is achievable as well, hence the inequality is in fact an equality. From here, a simple induction shows that $f(n) = 1-\frac{1}{2^{n-1}}$ for all $n \geq 1$. Hence the minimum time required to grow $n$ adult worms starting with only one is equal to $1-\frac{1}{2^{n-1}}$.