Project Euler Problem 532

Solution

Answer: 827306.56

Let the sphere have radius $1$, and let the bots initially lie on the latitude circle

$$x^2+y^2 = 0.999^2,$$

so their common colatitude is

$$\theta_0=\arcsin(0.999).$$

If there are $n$ bots, the longitude separation between neighboring bots is

$$\alpha=\frac{2\pi}{n}.$$

By symmetry, throughout the motion the bots remain equally spaced on a shrinking latitude circle.

For one bot at position $P$, chasing the next bot $Q$, the instantaneous velocity is the unit tangent vector along the great-circle geodesic from $P$ to $Q$.

A standard spherical-geometry computation gives the evolution equation

$$\frac{d\theta}{dt} = -\frac{\cos\theta,\sin(\alpha/2)} {\sqrt{1-\sin^2(\alpha/2)\sin^2\theta}}.$$

Since every bot moves with speed $1$, the length drawn by one bot equals the total time until $\theta=0$:

$$L_n = \int_0^{\theta_0} \frac{\sqrt{1-\sin^2(\alpha/2)\sin^2\theta}} {\sin(\alpha/2)\cos\theta} ,d\theta .$$

We now compute the smallest $n$ such that $L_n>1000$.

Using high-precision numerical integration:

from mpmath import mp

mp.dps = 50

theta0 = mp.asin(mp.mpf('0.999'))

def length_per_bot(n):
    k = mp.sin(mp.pi / n)

    f = lambda th: (
        mp.sqrt(1 - k*k * mp.sin(th)**2)
        / (k * mp.cos(th))
    )

    return mp.quad(f, [0, theta0])

n = 1
while True:
    n += 1
    L = length_per_bot(n)
    if L > 1000:
        break

total = n * L

print(n)
print(L)
print(total)

This yields:

$n=827$
length per bot $=1000.370689492285\ldots$
total length $=827306.5602101203\ldots$

For $n=826$, the length per bot is only $999.1610\ldots$, so $827$ is indeed minimal.

Therefore the required total length, rounded to two decimal places, is:

Answer: 827306.56