Project Euler Problem 724

Solution

Answer: 18128250110

Let $C_n$ be the coupon collector stopping time: the number of instructions issued until every drone has received at least one instruction.

Suppose the process stops after $C_n$ instructions.

Each instruction increases some drone’s speed by $1\text{ cm/s}$, and that extra speed remains active for the remaining duration of the experiment.

If an instruction is issued at second $t$, it contributes exactly

$$C_n - t + 1$$

centimetres to the final travel distance.

Therefore the total distance travelled by all packages is

$$\sum_{t=1}^{C_n} (C_n-t+1) = \frac{C_n(C_n+1)}{2}.$$

Since there are $n$ packages, the expected landing distance of a package is

$$E(n)=\frac1n \mathbb E!\left[\frac{C_n(C_n+1)}2\right].$$

For the coupon collector:

$$\mathbb E[C_n]=nH_n,$$

$$\operatorname{Var}(C_n)=n^2H_n^{(2)}-nH_n,$$

where

$$H_n=\sum_{k=1}^n\frac1k,\qquad H_n^{(2)}=\sum_{k=1}^n\frac1{k^2}.$$

Hence

$$\mathbb E[C_n^2] =\operatorname{Var}(C_n)+(\mathbb E[C_n])^2 =n^2(H_n^2+H_n^{(2)})-nH_n.$$

Substituting:

$$E(n) =\frac1{2n}\left(\mathbb E[C_n^2]+\mathbb E[C_n]\right) =\frac n2\left(H_n^2+H_n^{(2)}\right).$$

This matches the examples:

Now evaluate at $n=10^8$ using high-precision asymptotics:

$$H_n=\ln n+\gamma+\frac1{2n}-\frac1{12n^2}+\cdots$$

$$H_n^{(2)}=\frac{\pi^2}{6}-\frac1n+\frac1{2n^2}+\cdots$$

This gives

$$E(10^8)\approx 18128250110.418551844\ldots$$

Rounded to the nearest integer:

Answer: 18128250110