Detailed mathematical approach

Problem Summary

On turn \(k\), the random point is chosen uniformly as

$P=(1+ka,\ 1+kb),\qquad a,b\in[0,1],$

so \(P\) is uniform in the square

$Q_k=[1,k+1]\times[1,k+1].$

The score is \(k\) exactly when the distance from the origin rounds to \(k\), i.e.

$k-\frac12 \le \|P\| < k+\frac12.$

The program computes the expected total score up to \(k=100000\). The final numeric answer is intentionally omitted here.

Mathematical Approach

1) Expected score on one turn is an area. Since \(P\) is uniform in a square of area \(k^2\), the probability of scoring \(k\) equals

$\frac{\operatorname{area}\bigl(Q_k\cap \mathcal A_k\bigr)}{k^2},$

where \(\mathcal A_k\) is the annulus

$\mathcal A_k=\left\{(x,y):k-\frac12\le \sqrt{x^2+y^2}<k+\frac12\right\}.$

Therefore the expected contribution of turn \(k\) is

$k\cdot \frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k^2} =\frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k}.$

2) Why the upper edges of the square do not matter. Every point in the outer disk

$x^2+y^2\le \left(k+\frac12\right)^2$

has \(x\le k+\frac12\) and \(y\le k+\frac12\), which is strictly inside the square bounds \(x,y\le k+1\). So the only relevant constraints from \(Q_k\) are

$x\ge 1,\qquad y\ge 1.$

This is the key simplification behind the whole solution.

3) Introduce a cumulative area primitive. Define

$A(r)=\operatorname{area}\left\{(x,y):x\ge 1,\ y\ge 1,\ x^2+y^2\le r^2\right\}.$

Then the annulus area needed on turn \(k\) is just the difference

$\Delta_k=A\left(k+\frac12\right)-A\left(k-\frac12\right).$

So the full expectation becomes

$E_K=\sum_{k=1}^{K}\frac{\Delta_k}{k} =\sum_{k=1}^{K}\frac{A(k+1/2)-A(k-1/2)}{k}.$

This is exactly the summation implemented by the code.

4) Why \(A(r)=0\) for \(r\le \sqrt2\). The region \(x\ge 1,\ y\ge 1\) begins at the corner \((1,1)\), whose distance from the origin is

$\sqrt{1^2+1^2}=\sqrt2.$

If \(r\le \sqrt2\), the disk of radius \(r\) does not reach that corner, so there is no area at all inside the target region. Hence

$A(r)=0\qquad (r\le \sqrt2).$

5) Integral formula for \(A(r)\). For \(r>\sqrt2\), the circle \(x^2+y^2=r^2\) meets the line \(y=1\) at

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

Thus the desired area is the region between the arc

$y=\sqrt{r^2-x^2}$

and the line \(y=1\), for \(x\in[1,t]\). Therefore

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

6) Evaluate the integral in closed form. We use

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

Hence

$ A(r)= \left[ \frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right)-x \right]_{x=1}^{x=t}. $

At the upper limit, \(t=\sqrt{r^2-1}\) and \(\sqrt{r^2-t^2}=1\). Also

$\arcsin\frac{t}{r}=\frac{\pi}{2}-\arcsin\frac1r.$

Substituting and simplifying gives

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

This is the exact formula used by area_inside_square_and_circle.

Worked Examples

Example 1: the first turn. For \(k=1\), the inner radius is \(1/2\), so \(A(1/2)=0\). The outer radius is \(3/2\), hence

$\Delta_1=A\left(\frac32\right)\approx 0.0072246524.$

Since the turn score is weighted by \(1/k=1\), the expected contribution of turn 1 is the same tiny area. Geometrically, this is just the small lens near the corner \((1,1)\).

Example 2: checkpoint value. The source file checks that

$E_{10}\approx 10.20914,$

rounded to five digits after the decimal point. That is the numerical sanity check for the whole derivation.

Why the Code Is Correct

The solver does not simulate random throws. Instead, for each \(k\), it evaluates the exact outer area

$A\left(k+\frac12\right),$

subtracts the exact inner area

$A\left(k-\frac12\right),$

and divides by \(k\), which is precisely the expected contribution of the \(k\)-th turn. Summing these deterministic terms gives the exact expectation up to floating-point rounding.

Complexity Analysis

Each \(k\) requires only a constant number of elementary operations: one square root, one arcsine, and a few additions and multiplications. Therefore

$\text{time}=O(K),\qquad \text{memory}=O(1).$

The implementation uses long double and prints the final value to five decimal places.

Further Reading

1. Problem page: https://projecteuler.net/problem=285
2. Circular segment geometry: https://en.wikipedia.org/wiki/Circular_segment
3. Inverse-trigonometric antiderivatives: https://en.wikipedia.org/wiki/List_of_integrals_of_inverse_trigonometric_functions