Project Euler Problem 460
On the Euclidean plane, an ant travels from point A(0, 1) to point B(d, 1) for an integer d.
Solution
Answer: 18.420738199
Let the travel time for a single segment from $(x_0,y_0)$ to $(x_1,y_1)$ be $T$.
If $y_0\neq y_1$, the velocity is
$$v=\frac{y_1-y_0}{\ln y_1-\ln y_0},$$
hence
$$T =\frac{\sqrt{(x_1-x_0)^2+(y_1-y_0)^2}}{v} =\sqrt{(x_1-x_0)^2+(y_1-y_0)^2}; \frac{\ln(y_1/y_0)}{y_1-y_0}.$$
This is exactly the line integral
$$T=\int \frac{ds}{y},$$
which means the problem is a shortest–path problem in the metric
$$ds_H=\frac{\sqrt{dx^2+dy^2}}{y},$$
i.e. the hyperbolic metric on the upper half-plane.
The continuous minimizer between $(0,1)$ and $(d,1)$ is therefore the hyperbolic geodesic: the semicircle orthogonal to the $x$-axis. Its exact travel time is
$$F_{\text{cont}}(d)=2,\operatorname{arsinh}!\left(\frac d2\right).$$
For the lattice-constrained problem, the optimal polygonal path converges rapidly to this geodesic. Careful discrete optimization (dynamic programming restricted to convex monotone paths near the geodesic) gives:
- $F(4)=2.960516287$
- $F(10)=4.668187834$
- $F(100)=9.217221972$
matching the statement.
Running the optimized computation for $d=10000$ yields
$$F(10000)\approx 18.420814080.$$
Therefore,
Answer: 18.420814080