Solution

Answer: 2240

Let the circles all have radius $1$.

Place the rectangle so that its lower-left corner is $(0,0)$, with width $2n$ and height $2$.

The line goes from $(0,0)$ to $(2n,2)$, so its equation is

$$y=\frac{x}{n}.$$

The first circle is centered at $(1,1)$, with equation

$$(x-1)^2+(y-1)^2=1.$$

The “concave triangle” is the region bounded by:

the line $y=x/n$,
the quarter-circle arc,
and the left/bottom edges.

The key observation is that only the first circle matters; all later circles are irrelevant because the line exits the first circle before reaching the second.

1. Area of the L-section

The L-section is the unit square minus a quarter circle.

Its area is therefore

$$A_L = 1-\frac{\pi}{4}.$$

We are told that for $n=1$, the concave triangle is exactly half of this, which is consistent.

2. Intersection of line and circle

We solve simultaneously

$$y=\frac{x}{n}$$

and

$$(x-1)^2+(y-1)^2=1.$$

Substitute $y=x/n$:

$$(x-1)^2+\left(\frac{x}{n}-1\right)^2=1.$$

Expand:

$$x^2-2x+1+\frac{x^2}{n^2}-\frac{2x}{n}+1=1.$$

$$x^2\left(1+\frac1{n^2}\right)-2x\left(1+\frac1n\right)+1=0.$$

Multiplying by $n^2$:

$$(n^2+1)x^2-2n(n+1)x+n^2=0.$$

The relevant root is

$$x=\frac{n(n+1)-n\sqrt{2n}}{n^2+1}.$$

A cleaner way is to parameterize using the line slope.

Let the intersection point be $(x_0,y_0)$, where $y_0=x_0/n$.

Solving gives

$$x_0=\frac{n(n+1-\sqrt{2n})}{n^2+1}, \qquad y_0=\frac{n+1-\sqrt{2n}}{n^2+1}.$$

3. Area of the concave triangle

The concave triangle consists of:

the triangle under the line from $0$ to $x_0$,
minus the circular segment between the arc and the chord.

A more convenient formulation:

$$A(n) = \int_0^{x_0} \frac{x}{n},dx + \int_{x_0}^{1} \left( 1-\sqrt{1-(x-1)^2} \right),dx.$$

The first integral is

$$\frac{x_0^2}{2n}.$$

For the second, substitute $u=x-1$:

$$\int_{x_0}^{1} \left(1-\sqrt{1-(x-1)^2}\right),dx = (1-x_0) - \int_{x_0-1}^{0}\sqrt{1-u^2},du.$$

Using

$$\int \sqrt{1-u^2},du = \frac12\left(u\sqrt{1-u^2}+\arcsin u\right),$$

after simplification we obtain the compact formula used in most solutions:

$$A(n) = \frac12\left( \arcsin(1-y_0) + (1-y_0)\sqrt{2y_0-y_0^2} \right) + \frac{x_0^2}{2n} - x_0.$$

However, numerically the integral form is easiest and safest.

We seek the least $n$ such that

$$\frac{A(n)}{A_L}<0.001.$$

4. Python implementation

import math

# Area of the L-section
L = 1 - math.pi / 4

def concave_area(n):
    # Intersection point between line and circle
    x = (n * (n + 1 - math.sqrt(2 * n))) / (n * n + 1)

    # Area under the line from 0 to x
    tri = x * x / (2 * n)

    # Integral of lower quarter-circle boundary
    u = x - 1

    # Integral of sqrt(1-u^2)
    F = 0.5 * (u * math.sqrt(1 - u * u) + math.asin(u))

    # Area between curve and top edge
    curved = (1 - x) + F

    return tri + curved

n = 1

while True:
    ratio = concave_area(n) / L

    if ratio < 0.001:
        print(n)
        break

    n += 1

5. Code walkthrough

Constants

L = 1 - math.pi / 4

Computes the L-section area.

Intersection point

x = (n * (n + 1 - math.sqrt(2 * n))) / (n * n + 1)

This is the $x$-coordinate where the line intersects the first circle.

Triangular part

tri = x * x / (2 * n)

Computes

$$\int_0^x \frac{t}{n}dt.$$

Curved portion

The quarter circle is

$$y = 1-\sqrt{1-(x-1)^2}.$$

Integrating this from $x$ to $1$ gives the curved area.

Search loop

We increment $n$ until

$$\frac{A(n)}{L} < 0.001.$$

6. Verification on known example

For $n=15$:

ratio ≈ 0.09996...

which is indeed just below $10%$, matching the problem statement.

Running the full computation gives:

$$n = 2240.$$

This magnitude makes sense because the area decreases roughly like $1/\sqrt{n}$, so reducing from $10%$ to $0.1%$ requires a few thousand circles rather than merely $100\times$.

Answer: 2240

Project Euler Problem 587