Detailed mathematical approach

Problem Summary

Let

$R=\left\{(x,y):-1\le x\le 1,\ 0\le y\le 1-x^4\right\}.$

We want the largest-area \(n\)-gon contained in this region for \(n=101\). The implementations represent the polygon by ordered boundary points

$-1=x_0<x_1<\cdots<x_{n-1}=1,$

with vertices

$P_i=\left(x_i,\,1-x_i^4\right).$

Because \(1-x^4\) is concave on \([-1,1]\), every chord between two such boundary points stays below the curve, so an increasing knot sequence automatically defines an inscribed polygon.

Mathematical Approach

Write \(f(x)=1-x^4\). The polygon area depends only on the \(x\)-coordinates of the chosen boundary points, so the problem becomes a constrained optimization in one dimension.

Step 1: Write the polygon area as a trapezoidal sum

The edge from \(P_i\) to \(P_{i+1}\) contributes the area of a trapezoid with heights \(f(x_i)\) and \(f(x_{i+1})\) and width \(x_{i+1}-x_i\). Therefore

$A(x_1,\dots,x_{n-2})=\sum_{i=0}^{n-2}\frac{f(x_i)+f(x_{i+1})}{2}\,(x_{i+1}-x_i).$

After substituting \(f(x)=1-x^4\), this becomes

$A=\sum_{i=0}^{n-2}\frac{2-x_i^4-x_{i+1}^4}{2}\,(x_{i+1}-x_i).$

This is exactly the quantity accumulated by the numerical solver after the knots have converged.

Step 2: Isolate one interior knot

If \(x_i\) is an interior knot, only the two adjacent segments depend on it. With

$a=x_{i-1},\qquad t=x_i,\qquad b=x_{i+1},$

the local contribution is

$\Phi_i(t)=\frac{2-a^4-t^4}{2}(t-a)+\frac{2-t^4-b^4}{2}(b-t).$

Differentiating with respect to \(t\) gives

$\Phi_i'(t)=\frac{b^4-a^4}{2}-2t^3(b-a).$

At an optimal configuration every interior knot must satisfy \(\Phi_i'(x_i)=0\).

Step 3: Derive the stationary equation

Setting the derivative to zero yields

$4x_i^3(x_{i+1}-x_{i-1})=x_{i+1}^4-x_{i-1}^4.$

Solving for \(x_i\) gives the update target

$x_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}.$

This has a useful geometric interpretation. By the mean value theorem applied to \(u^4\), there exists \(\xi\in(x_{i-1},x_{i+1})\) such that

$\frac{x_{i+1}^4-x_{i-1}^4}{x_{i+1}-x_{i-1}}=4\xi^3.$

Hence the cubic-root target is exactly that intermediate point \(\xi\), so it lies between the two neighboring knots.

Step 4: Convert the optimality condition into an iteration

The exact stationary system is nonlinear, so the implementations solve it numerically. They start from the uniformly spaced mesh

$x_i=-1+\frac{2i}{n-1}\qquad(0\le i\le n-1)$

and then sweep through the interior knots with a relaxed fixed-point step

$x_i\leftarrow x_i+\omega\left(\widehat{x}_i-x_i\right),\qquad \omega=0.5,$

where

$\widehat{x}_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}.$

The sweep is Gauss-Seidel style: once one knot is updated, its new value is immediately reused when the next knot is processed. Damping with \(\omega=0.5\) stabilizes the iteration while preserving the same fixed points.

Step 5: Check convergence and evaluate the area

After each full sweep, the implementation records the largest coordinate change. Once that maximum update falls below a tiny tolerance, the knot sequence is treated as converged. The area is then computed from the same trapezoidal sum as in Step 1. The C++ implementation also checks that the knots remain strictly increasing and that the residual

$4x_i^3(x_{i+1}-x_{i-1})-\left(x_{i+1}^4-x_{i-1}^4\right)$

is numerically negligible for every interior knot.

Worked Example: \(n=3\)

For a triangle there is only one interior knot, say \(x_1=t\). The area becomes

$A(t)=\frac{1-t^4}{2}(t+1)+\frac{1-t^4}{2}(1-t)=1-t^4.$

This is maximized at \(t=0\), giving the triangle with vertices \((-1,0)\), \((0,1)\), and \((1,0)\). Therefore

$G(3)=1.$

This is the first benchmark used to confirm that the numerical method is behaving correctly.

How the Code Works

The C++, Python, and Java implementations all follow the same numerical plan. They initialize evenly spaced knots, repeatedly compute the cubic-root target from the two neighboring knots, and move halfway toward that target. The stopping condition is the largest knot displacement in one sweep. After convergence, the implementation sums the segment-wise trapezoid areas and prints the result for \(n=101\).

The only language-level numerical difference is how the real cube root is obtained. This matters on the left half of the interval because the target can be negative, so the implementation must stay on the real line rather than rely on a complex-valued fractional power convention. The C++ implementation also checks the numerical checkpoints \(G(3)=1\) and \(G(5)\approx 1.477309771\).

Complexity Analysis

With \(n\) vertices, one sweep updates \(n-2\) interior knots, so its cost is \(O(n)\). Evaluating the final area also costs \(O(n)\). If \(I\) sweeps are needed for convergence, the total running time is \(O(nI)\), and the memory usage is \(O(n)\) because only the knot coordinates are stored.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=897
2. Trapezoidal rule: Wikipedia - Trapezoidal rule
3. Fixed-point iteration: Wikipedia - Fixed-point iteration
4. Mean value theorem: Wikipedia - Mean value theorem
5. Concave function: Wikipedia - Concave function