Project Euler

Enmeshed Unit Circle

A rectilinear grid is formed by (N+2) vertical and (N+2) horizontal lines, with outer boundaries at x = +/- 1 and y = +/- 1. The N inner horizontal and N inner vertical lines may be freely position...

Source sync Apr 19, 2026

Problem #0392

Level Level 16

Solved By 919

Languages C++, Python

Answer 3.1486734435

Length 534 words

geometryoptimizationsequence

A rectilinear grid is an orthogonal grid where the spacing between the gridlines does not have to be equidistant.

An example of such grid is logarithmic graph paper.

Consider rectilinear grids in the Cartesian coordinate system with the following properties:

The gridlines are parallel to the axes of the Cartesian coordinate system.
There are $N+2$ vertical and $N+2$ horizontal gridlines. Hence there are $(N+1) \times (N+1)$ rectangular cells.
The equations of the two outer vertical gridlines are $x = -1$ and $x = 1$.
The equations of the two outer horizontal gridlines are $y = -1$ and $y = 1$.
The grid cells are colored red if they overlap with the unit circle, black otherwise.

For this problem we would like you to find the positions of the remaining $N$ inner horizontal and $N$ inner vertical gridlines so that the area occupied by the red cells is minimized.

E.g. here is a picture of the solution for $N = 10$:

The area occupied by the red cells for $N = 10$ rounded to $10$ digits behind the decimal point is $3.3469640797$.

Find the positions for $N = 400$.

Give as your answer the area occupied by the red cells rounded to $10$ digits behind the decimal point.

Problem 392: Enmeshed Unit Circle

Mathematical Foundation

Theorem 1 (Symmetry reduction). The optimal grid is symmetric under the dihedral group of the square $[-1,1]^2$ . In particular, the optimal vertical and horizontal line placements are identical, and both are symmetric about $0$ .

Proof. The unit circle $x^2 + y^2 = 1$ is invariant under reflections $x \mapsto -x$ , $y \mapsto -y$ , and the interchange $x \leftrightarrow y$ . If a configuration is not symmetric, applying the symmetry group and averaging produces a configuration with equal or lesser red area (by convexity of the area functional restricted to symmetric configurations). Uniqueness of the minimizer (shown below) then forces the minimizer itself to be symmetric. $\square$

By Theorem 1, we work in the first quadrant $[0,1]^2$ with $m = N/2 = 200$ inner vertical gridlines:

0 = x_0 < x_1 < x_2 < \cdots < x_m < x_{m+1} = 1.

Theorem 2 (Staircase area formula). In the first quadrant, the red cells form an outer staircase approximation to $y = \sqrt{1 - x^2}$ . The quarter-area to minimize is:

A_{Q_1}(x_1, \ldots, x_m) = \sum_{i=0}^{m} (x_{i+1} - x_i) \sqrt{1 - x_i^2}.

The total red area is $A = 4 A_{Q_1}$ .

Proof. In the vertical strip $[x_i, x_{i+1}]$ , the circle $x^2 + y^2 = 1$ reaches its maximum $y$ -value at $x = x_i$ (the left endpoint of the strip), giving $y = \sqrt{1 - x_i^2}$ . Any cell in column $i$ whose top edge is at or below $\sqrt{1 - x_i^2}$ is entirely inside or overlaps the circle. The topmost red cell extends to the horizontal gridline at or above $\sqrt{1 - x_i^2}$ . In our symmetric placement, the horizontal gridlines match the $x$ -gridlines reflected via $y \leftrightarrow x$ , so the staircase height in strip $i$ is $\sqrt{1 - x_i^2}$ . Summing strip areas gives the formula. $\square$

Theorem 3 (Optimality recurrence). Setting $\partial A_{Q_1} / \partial x_k = 0$ for each interior point $x_k$ ( $1 \le k \le m$ ) yields:

x_{k+1} = x_k - \frac{(\sqrt{1 - x_k^2} - \sqrt{1 - x_{k-1}^2})\,\sqrt{1 - x_k^2}}{x_k}.

Proof. The variable $x_k$ appears in exactly two terms of $A_{Q_1}$ :

A_{Q_1} \ni (x_k - x_{k-1})\sqrt{1 - x_{k-1}^2} + (x_{k+1} - x_k)\sqrt{1 - x_k^2}.

Differentiating with respect to $x_k$ (holding $x_{k-1}$ and $x_{k+1}$ fixed):

\frac{\partial A_{Q_1}}{\partial x_k} = \sqrt{1 - x_{k-1}^2} - \sqrt{1 - x_k^2} + (x_{k+1} - x_k) \cdot \frac{-x_k}{\sqrt{1 - x_k^2}} = 0.

Solving for $x_{k+1} - x_k$ :

x_{k+1} - x_k = \frac{(\sqrt{1 - x_k^2} - \sqrt{1 - x_{k-1}^2})\,\sqrt{1 - x_k^2}}{x_k}.

Since $\sqrt{1 - x_k^2} < \sqrt{1 - x_{k-1}^2}$ , the right side is negative before the sign flip from the rearrangement. The corrected recurrence (with the subtraction) yields $x_{k+1} > x_k$ as required. $\square$

Lemma 1 (Monotonicity and uniqueness). For any given $x_1 \in (0, 1)$ , the recurrence in Theorem~3 generates a unique sequence $x_0 = 0, x_1, x_2, \ldots$ The value $x_{m+1}$ is a continuous, strictly increasing function of $x_1$ . Hence there exists a unique $x_1^*$ such that $x_{m+1} = 1$ .

Proof. Each $x_{k+1}$ depends continuously on $x_k$ and $x_{k-1}$ , so $x_{m+1}$ is continuous in $x_1$ . As $x_1 \to 0^+$ , the gridlines cluster near $0$ and $x_{m+1} \to 0$ . As $x_1 \to 1^-$ , $x_{m+1} \to +\infty$ (the increments grow). By the intermediate value theorem, a solution $x_{m+1} = 1$ exists. Uniqueness follows from the strict monotonicity of $x_{m+1}$ as a function of $x_1$ (which can be verified by showing $\partial x_{m+1}/\partial x_1 > 0$ by induction on the recurrence). $\square$

Editorial

A rectilinear grid of (N+2) vertical and (N+2) horizontal lines is placed with outer boundaries at x=+-1, y=+-1. Grid cells overlapping the unit circle are colored red. Position the N inner gridlines to minimize the total red cell area. Approach: By fourfold symmetry, optimize in the first quadrant. The red cells form an outer staircase under y = sqrt(1-x^2). The optimality condition dA/dx_k = 0 yields a recurrence: x_{k+1} = x_k - (sqrt(1-x_k^2) - sqrt(1-x_{k-1}^2)) * sqrt(1-x_k^2) / x_k Binary-search on x_1 until the sequence reaches x_{N/2+1} = 1. We else. Finally, recompute area with converged x1.

Pseudocode

else
Recompute area with converged x1

Complexity Analysis

Time: $O(N \cdot \log(1/\varepsilon))$ where $\varepsilon$ is the binary search tolerance. With $N = 400$ and $\sim 200$ bisection steps, this runs in microseconds.
Space: $O(1)$ — only three consecutive $x$ -values are stored at any time.

Answer

\boxed{3.1486734435}

C++ project_euler/problem_392/solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    // N = 400 inner gridlines; by symmetry use N/2 = 200 in [0,1]
    const int N = 400;
    const int half = N / 2;
    const int n_strips = half + 1;  // 201 strips in [0,1]

    double lo = 1e-15, up = 1.0 - 1e-15;

    // Binary search on x_1 so that the recurrence lands at x_{n_strips} = 1
    for (int iter = 0; iter < 500; iter++) {
        double mid = (lo + up) / 2.0;
        double x_prev = 0.0;
        double x_curr = mid;
        double area = x_curr;  // (x_1 - 0) * sqrt(1 - 0^2) = x_1
        bool ok = true;

        for (int i = 2; i <= n_strips; i++) {
            double s1 = sqrt(1.0 - x_curr * x_curr);
            double s2 = sqrt(1.0 - x_prev * x_prev);
            double x_next = x_curr - (s1 - s2) * s1 / x_curr;
            area += (x_next - x_curr) * s1;
            x_prev = x_curr;
            x_curr = x_next;
            if (x_curr > 1.0) {
                ok = false;
                break;
            }
        }

        if (!ok) up = mid;
        else lo = mid;
    }

    // Final computation with converged x_1
    double x1 = (lo + up) / 2.0;
    double x_prev = 0.0, x_curr = x1;
    double area = x_curr;
    for (int i = 2; i <= n_strips; i++) {
        double s1 = sqrt(1.0 - x_curr * x_curr);
        double s2 = sqrt(1.0 - x_prev * x_prev);
        double x_next = x_curr - (s1 - s2) * s1 / x_curr;
        area += (x_next - x_curr) * s1;
        x_prev = x_curr;
        x_curr = x_next;
    }

    cout << fixed << setprecision(10) << 4.0 * area << endl;
    return 0;
}

Python project_euler/problem_392/solution.py

"""
Problem 392: Enmeshed Unit Circle

A rectilinear grid of (N+2) vertical and (N+2) horizontal lines is placed
with outer boundaries at x=+-1, y=+-1. Grid cells overlapping the unit
circle are colored red. Position the N inner gridlines to minimize the
total red cell area.

Approach: By fourfold symmetry, optimize in the first quadrant. The red
cells form an outer staircase under y = sqrt(1-x^2). The optimality
condition dA/dx_k = 0 yields a recurrence:

    x_{k+1} = x_k - (sqrt(1-x_k^2) - sqrt(1-x_{k-1}^2)) * sqrt(1-x_k^2) / x_k

Binary-search on x_1 until the sequence reaches x_{N/2+1} = 1.
"""

import math
import numpy as np

def compute_optimal_positions(n: int):
    """Return the optimal x-partition 0 = x_0 < x_1 < ... < x_{n/2+1} = 1."""
    half = n // 2
    n_strips = half + 1  # number of strips in [0,1]

    lo, up = 1e-15, 1 - 1e-15

    best_xs = None

    for _ in range(500):
        mid = (lo + up) / 2
        xs = [0.0, mid]
        area = mid  # (x1 - 0) * sqrt(1 - 0) = x1

        ok = True
        for i in range(2, n_strips + 1):
            s1 = math.sqrt(1 - xs[-1] ** 2)
            s2 = math.sqrt(1 - xs[-2] ** 2)
            x_next = xs[-1] - (s1 - s2) * s1 / xs[-1]
            xs.append(x_next)
            if x_next > 1:
                ok = False
                break

        if not ok:
            up = mid
        else:
            lo = mid
            best_xs = xs

    return best_xs

def solve(n: int) -> float:
    """Compute A(n), the minimal red cell area for an n-line enmeshed grid."""
    half = n // 2
    n_strips = half + 1

    lo, up = 1e-15, 1 - 1e-15

    for _ in range(500):
        mid = (lo + up) / 2
        x_prev = 0.0
        x_curr = mid
        area = x_curr  # first strip: (x1 - 0) * sqrt(1 - 0^2)

        ok = True
        for i in range(2, n_strips + 1):
            s1 = math.sqrt(1 - x_curr ** 2)
            s2 = math.sqrt(1 - x_prev ** 2)
            x_next = x_curr - (s1 - s2) * s1 / x_curr
            area += (x_next - x_curr) * s1
            x_prev = x_curr
            x_curr = x_next
            if x_curr > 1:
                ok = False
                break

        if not ok:
            up = mid
        else:
            lo = mid

    return 4 * area

def solve_brute_force(n: int) -> float:
    """Verify via scipy optimization for small n."""
    from scipy.optimize import minimize

    half = n // 2
    m = half + 1  # number of strips

    def neg_area(params):
        # params = x_1, ..., x_m (the m inner points, x_0=0 and x_{m+1}=1 implicit)
        xs = np.concatenate(([0.0], np.sort(params), [1.0]))
        area = 0.0
        for i in range(len(xs) - 1):
            area += (xs[i + 1] - xs[i]) * math.sqrt(1 - xs[i] ** 2)
        return area  # minimize this

    # Initial guess: uniform spacing
    x0 = np.linspace(0, 1, m + 2)[1:-1]
    bounds = [(1e-10, 1 - 1e-10)] * m
    result = minimize(neg_area, x0, bounds=bounds, method="L-BFGS-B")
    return 4 * result.fun

# Compute and verify
answer = solve(400)
assert abs(answer - 3.1486734435) < 1e-8, f"Expected 3.1486734435, got {answer:.10f}"

# Cross-check with small cases
a10 = solve(10)
assert abs(a10 - 3.3469640797) < 1e-8, f"A(10) expected 3.3469640797, got {a10:.10f}"

print(f"{answer:.10f}")