Project Euler Problem 285

Solution

Answer: 157055.80999

Let

$$x = ka+1,\qquad y = kb+1,$$

where $a,b\sim U[0,1]$.

Then $(x,y)$ is uniformly distributed on the square

$$[1,k+1]\times[1,k+1],$$

whose area is $k^2$.

Albert scores $k$ points exactly when

$$k-\tfrac12 \le \sqrt{x^2+y^2} < k+\tfrac12.$$

So we need the area of the portion of the square lying inside the annulus

$$(k-\tfrac12)^2 \le x^2+y^2 < (k+\tfrac12)^2.$$

---

1. Geometric probability

Define

$$A(R)=\text{area}\left({(x,y)\in[1,\infty)^2:x^2+y^2\le R^2}\right).$$

For $R>1$, the circle intersects the line $y=1$ at

$$x=\sqrt{R^2-1}.$$

Hence

$$A(R)=\int_1^{\sqrt{R^2-1}} \left(\sqrt{R^2-x^2}-1\right),dx.$$

Using

$$\int \sqrt{R^2-x^2},dx = \frac12\left( x\sqrt{R^2-x^2} + R^2\arcsin\frac{x}{R} \right),$$

we obtain after simplification:

$$A(R) = 1-\sqrt{R^2-1} + R^2\left( \frac{\pi}{4}-\arcsin\frac1R \right).$$

So the desired probability for a fixed $k$ is

$$P_k = \frac{ A(k+\tfrac12)-A(k-\tfrac12) }{k^2}.$$

The expected score contribution from turn $k$ is therefore

$$E_k = kP_k = \frac{ A(k+\tfrac12)-A(k-\tfrac12) }{k}.$$

Thus the total expectation is

$$E = \sum_{k=1}^{10^5} \frac{ A(k+\tfrac12)-A(k-\tfrac12) }{k}.$$

---

2. Python implementation

import math

def A(R):
    # For R <= 1 the region is empty
    if R <= 1.0:
        return 0.0

    return (
        1.0
        - math.sqrt(R * R - 1.0)
        + R * R * (math.pi / 4.0 - math.asin(1.0 / R))
    )

def expected_value(n):
    total = 0.0

    for k in range(1, n + 1):
        outer = A(k + 0.5)
        inner = A(k - 0.5)

        total += (outer - inner) / k

    return total

# Check the example from the problem
print(round(expected_value(10), 5))

# Compute the required answer
ans = expected_value(100000)

print(f"{ans:.5f}")

---

3. Code walkthrough

Function A(R)

def A(R):

Computes the area inside the circle of radius $R$ restricted to the first-quadrant strip $x,y\ge1$.

---

if R <= 1.0:
    return 0.0

If the radius is too small, the circle never reaches the square corner $(1,1)$, so the area is zero.

---

return (
    1.0
    - math.sqrt(R * R - 1.0)
    + R * R * (math.pi / 4.0 - math.asin(1.0 / R))
)

Direct implementation of the derived closed formula.

---

Main summation

for k in range(1, n + 1):

Iterates over all turns.

---

outer = A(k + 0.5)
inner = A(k - 0.5)

Computes the annulus slice corresponding to rounding to $k$.

---

total += (outer - inner) / k

Adds the expected contribution

$$\frac{A(k+1/2)-A(k-1/2)}{k}.$$

---

4. Verification

For $n=10$, the program gives

$$10.20914$$

matching the value stated in the problem.

For $n=100000$, the result is stable to many decimal places and behaves correctly asymptotically (the terms decay roughly like $1/k$).

---

Answer: 157055.80999