Detailed mathematical approach

Problem Summary

We must travel from \(A\) to \(B\), which are 100 leagues apart horizontally. Between them lies a marsh split into five parallel strips. Travel speed is \(10\) on dry land, then \(9,8,7,6,5\) in the five marsh strips, and \(10\) again after leaving the marsh. Because the strip boundaries are oblique, the fastest route is not the naive straight-east path; we need the true minimum travel time, rounded to 10 decimal places.

Mathematical Approach

The implementation turns the geometry into a layered-medium optimization problem. After one coordinate rotation, every region has a fixed thickness, the optimal path is piecewise linear, and the whole problem reduces to solving one monotone equation in a single real parameter.

Step 1: Rotate Coordinates and Measure the Layers

Use the rotated coordinates

$u=\frac{x+y}{\sqrt{2}},\qquad v=\frac{x-y}{\sqrt{2}}.$

In these coordinates, the strip boundaries become horizontal, so the path crosses seven layers in a fixed order: dry land, five marsh strips, dry land.

The total displacement from \(A\) to \(B\) becomes

$\Delta u=\Delta v=\frac{100}{\sqrt{2}}=50\sqrt{2}.$

The marsh itself contributes total \(v\)-thickness \(50\), divided into five equal strips, so each marsh layer has thickness \(10\). The remaining \(v\)-distance belongs to the dry land on the two sides:

$2d_0+50=50\sqrt{2},\qquad d_0=25(\sqrt{2}-1).$

Therefore the seven layer thicknesses are

$\Delta v=(d_0,10,10,10,10,10,d_0),$

and the corresponding speeds are

$s=(10,9,8,7,6,5,10).$

Step 2: Write the Time Formula in One Layer

Inside any one layer the speed is constant, so the time-minimizing segment between two boundary points is a straight line. Let the segment in layer \(i\) make angle \(\theta_i\) with the \(v\)-axis, and let its layer thickness be \(\Delta v_i\).

Its tangential displacement is

$\Delta u_i=\Delta v_i\tan\theta_i,$

its geometric length is

$\ell_i=\frac{\Delta v_i}{\cos\theta_i},$

and its travel time is

$t_i=\frac{\ell_i}{s_i}=\frac{\Delta v_i}{s_i\cos\theta_i}.$

If we describe the whole path by the seven tangential displacements, then the total time is

$T=\sum_{i=1}^{7}\frac{\sqrt{\Delta v_i^2+\Delta u_i^2}}{s_i},$

subject to the horizontal constraint

$\sum_{i=1}^{7}\Delta u_i=U,\qquad U=\frac{100}{\sqrt{2}}.$

Step 3: Apply Fermat's Principle and Recover Snell's Law

We now minimize \(T\) with the single linear constraint \(\sum \Delta u_i=U\). Introduce a Lagrange multiplier \(k\). Differentiating with respect to each \(\Delta u_i\) gives

$\frac{\Delta u_i}{s_i\sqrt{\Delta v_i^2+\Delta u_i^2}}=k.$

But

$\sin\theta_i=\frac{\Delta u_i}{\sqrt{\Delta v_i^2+\Delta u_i^2}},$

so the optimal path satisfies the same constant-ratio condition in every layer:

$\frac{\sin\theta_i}{s_i}=k.$

This is exactly Snell's law written in terms of speed rather than refractive index. One constant \(k\) determines every angle of the optimal broken line.

Step 4: Reduce Everything to One Equation in \(k\)

From \(\sin\theta_i=ks_i\), we get

$\cos\theta_i=\sqrt{1-k^2s_i^2},$

and therefore

$\Delta u_i=\Delta v_i\frac{ks_i}{\sqrt{1-k^2s_i^2}},$

$t_i=\frac{\Delta v_i}{s_i\sqrt{1-k^2s_i^2}}.$

So \(k\) must solve

$f(k)=\sum_{i=1}^{7}\Delta v_i\frac{ks_i}{\sqrt{1-k^2s_i^2}}=\frac{100}{\sqrt{2}}.$

Because the maximum speed is \(10\), the valid interval is

$0\le k<\frac{1}{10}.$

Moreover, each summand is increasing, and

$f'(k)=\sum_{i=1}^{7}\frac{\Delta v_i s_i}{(1-k^2s_i^2)^{3/2}}>0,$

so the equation has a unique solution. That monotonicity is why bisection works immediately and robustly.

Step 5: Worked Example: The Straight-East Reference Path

A useful checkpoint is the path that keeps moving due east in the original coordinates. After rotation, that means \(\Delta u_i=\Delta v_i\) in every layer, so \(\theta_i=45^\circ\) throughout.

Hence

$T_{\text{east}}=\sum_{i=1}^{7}\frac{\Delta v_i}{s_i\cos45^\circ}=\sqrt{2}\sum_{i=1}^{7}\frac{\Delta v_i}{s_i}.$

Substituting the seven layer data gives

$T_{\text{east}}=\sqrt{2}\left(\frac{d_0}{10}+\frac{10}{9}+\frac{10}{8}+\frac{10}{7}+\frac{10}{6}+\frac{10}{5}+\frac{d_0}{10}\right)\approx 13.4738.$

This is not the optimal answer, but it is an excellent numerical sanity check because it is easy to compute independently and the C++ implementation verifies it before reporting the optimized time.

Step 6: Final Expression for the Minimum Time

Once the unique root \(k\) is found, the minimum travel time is

$T_{\min}=\sum_{i=1}^{7}\frac{\Delta v_i}{s_i\sqrt{1-k^2s_i^2}}.$

The numerical search uses a fixed number of bisection iterations, so the final midpoint is far more accurate than the 10 decimal places required by the problem.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. First they store the seven layer thicknesses and seven speeds implied by the rotated geometry. Next they evaluate one expression that returns the total \(u\)-displacement for a candidate value of \(k\), and another that returns the corresponding travel time. They then perform bisection on the interval \([0,0.1]\): if the trial displacement is too small, the lower bound moves up; otherwise the upper bound moves down. After 200 iterations, the midpoint gives a highly accurate approximation of the unique root, and the total time is evaluated there and printed with 10 digits after the decimal point. The C++ implementation also checks the straight-east reference value \(13.4738\) before producing the final answer.

Complexity Analysis

The number of layers is fixed at \(7\), and the number of bisection steps is fixed at \(200\). Each iteration evaluates a seven-term sum, so the running time is bounded by a small constant and the memory usage is also constant. In asymptotic notation for this specific problem, the implementation is \(O(1)\) in time and \(O(1)\) in space.

Footnotes and References

1. Project Euler problem page: Project Euler 607
2. Snell's law: Wikipedia - Snell's law
3. Fermat's principle: Wikipedia - Fermat's principle
4. Bisection method: Wikipedia - Bisection method
5. Calculus of variations: Wikipedia - Calculus of variations