EP Ethan Pham AI/ML engineer publishing Project Euler proofs, ICPC and IOI archives, and theory-heavy engineering notes.
All Euler problems
Project Euler

Squares on the Line

n points are chosen independently and uniformly on [0, 1]. Compute expected geometric quantities related to their configuration (gaps, spacing, maximum gap).

Source sync Apr 19, 2026
Problem #0644
Level Level 36
Solved By 183
Languages C++, Python
Answer 20.11208767
Length 335 words
probabilitygeometryanalytic_math
Problem statement

Problem Statement

This archive keeps the full statement, math, and original media on the page.

Sam and Tom are trying a game of (partially) covering a given line segment of length \(L\) by taking turns in placing unit squares onto the line segment.

As illustrated below, the squares may be positioned in two different ways, either "straight" by placing the midpoints of two opposite sides on the line segment, or "diagonal" by placing two opposite corners on the line segment. Newly placed squares may touch other squares, but are not allowed to overlap any other square laid down before.

The player who is able to place the last unit square onto the line segment wins.

PIC

With Sam starting each game by placing the first square, they quickly realise that Sam can easily win every time by placing the first square in the middle of the line segment, making the game boring.

Therefore they decide to randomise Sam’s first move, by first tossing a fair coin to determine whether the square will be placed straight or diagonal onto the line segment and then choosing the actual position on the line segment randomly with all possible positions being equally likely. Sam’s gain of the game is defined to be 0 if he loses the game and \(L\) if he wins. Assuming optimal play of both players after Sam’s initial move, you can see that Sam’s expected gain, called \(e(L)\), is only dependent on the length of the line segment.

For example, if \(L=2\), Sam will win with a probability of \(1\), so \(e(2)= 2\).

Choosing \(L=4\), the winning probability will be \(0.33333333\) for the straight case and \(0.22654092\) for the diagonal case, leading to \(e(4)=1.11974851\) (rounded to \(8\) digits after the decimal point each).

Being interested in the optimal value of \(L\) for Sam, let’s define \(f(a,b)\) to be the maximum of \(e(L)\) for some \(L \in [a,b]\).

You are given \(f(2,10)=2.61969775\), being reached for \(L= 7.82842712\), and \(f(10,20)= 5.99374121\) (rounded to \(8\) digits each).

Find \(f(200,500)\), rounded to \(8\) digits after the decimal point.

Problem 644 content is attributed to Project Euler and included here under the CC BY-NC-SA 4.0 license.

Open official problem License details

Problem 644: Squares on the Line

Mathematical Analysis

Order Statistics

Let U(1)≤U(2)≤⋯≤U(n)U_{(1)} \le U_{(2)} \le \cdots \le U_{(n)} be the order statistics of nn uniform samples on [0,1][0,1].

E[U(k)]=kn+1,Var(U(k))=k(n+1−k)(n+1)2(n+2)(1)\mathbb{E}[U_{(k)}] = \frac{k}{n+1}, \quad \text{Var}(U_{(k)}) = \frac{k(n+1-k)}{(n+1)^2(n+2)} \tag{1}

Spacings

The spacings Di=U(i)−U(i−1)D_i = U_{(i)} - U_{(i-1)} (with U(0)=0U_{(0)} = 0, U(n+1)=1U_{(n+1)} = 1) satisfy:

E[Di]=1n+1,for all i=1,…,n+1(2)\mathbb{E}[D_i] = \frac{1}{n+1}, \quad \text{for all } i = 1, \ldots, n+1 \tag{2}

The spacings are exchangeable (identically distributed but not independent).

Maximum Spacing

E[max⁡iDi]=Hnn=1n∑k=1n1k∼ln⁡nn(3)\mathbb{E}[\max_i D_i] = \frac{H_n}{n} = \frac{1}{n}\sum_{k=1}^{n} \frac{1}{k} \sim \frac{\ln n}{n} \tag{3}

Geometric Probability

The probability that a random triangle formed by 3 of the nn points is “well-formed” (e.g., sides satisfy certain constraints) reduces to integration over order statistics.

Derivation

Integration over the simplex 0≤x1≤⋯≤xn≤10 \le x_1 \le \cdots \le x_n \le 1 with appropriate Jacobian n!n!.

Proof of Correctness

Theorem. E[U(k)]=k/(n+1)\mathbb{E}[U_{(k)}] = k/(n+1).

Proof. The joint density of order statistics is n!n! on the simplex. By symmetry and the beta integral: E[U(k)]=∫01x⋅n!(k−1)!(n−k)!xk−1(1−x)n−kdx=B(k+1,n−k+1)/B(k,n−k+1)=k/(n+1)\mathbb{E}[U_{(k)}] = \int_0^1 x \cdot \frac{n!}{(k-1)!(n-k)!} x^{k-1}(1-x)^{n-k}dx = \text{B}(k+1,n-k+1)/\text{B}(k,n-k+1) = k/(n+1). □\square

Complexity Analysis

Closed-form formulas: O(1)O(1) per query. Simulation: O(Mnlog⁡n)O(Mn\log n) for MM trials.

Additional Analysis

Beta distribution: U_{(k)} ~ Beta(k, n+1-k). Joint density: n! on simplex. Maximum spacing: E[max D_i] ~ H_n/n ~ ln(n)/n.

Order Statistics

U_{(k)} ~ Beta(k, n+1-k) with E[U_{(k)}] = k/(n+1), Var = k(n+1-k)/((n+1)^2(n+2)).

Spacings

D_i = U_{(i+1)} - U_{(i)} with E[D_i] = 1/(n+1), Var = n/((n+1)^2(n+2)).

Exponential Connection

If X_1,…,X_{n+1} ~ iid Exp(1), then (X_i/sum X_j) has the same distribution as the spacings D_i. This simplifies computations.

Maximum Spacing

E[max D_i] = sum_{k=1}^{n+1} (-1)^{k+1} C(n+1,k)/k ~ ln(n+1)/(n+1) for large n.

Joint Distribution

For two order statistics U_{(j)} and U_{(k)} with j < k, the joint density is:

f(x,y) = n!/((j-1)!(k-j-1)!(n-k)!) * x^{j-1}(y-x)^{k-j-1}(1-y)^{n-k}

for 0 < x < y < 1.

Expected Product

E[U_{(j)}*U_{(k)}] = j(k+1)/((n+1)(n+2)) for j <= k.

Spacing Covariance

Cov(D_i, D_j) = -1/((n+1)^2(n+2)) for i != j. The negative covariance reflects that larger spacings in one place force smaller spacings elsewhere.

Application

These formulas enable exact computation of expected geometric quantities (distances, areas, angles) formed by random points on [0,1].

Minimum Spacing

E[min D_i] = 1/((n+1)*C(n+1,1)) = 1/(n+1). More precisely, P(min D_i > x) = (1-(n+1)x)^n for x < 1/(n+1), giving E[min D_i] = 1/(n(n+1)).

Cover Time

The expected number of random points needed to epsilon-cover [0,1] (every point within epsilon of some sample) is ~ (1/epsilon)*ln(1/epsilon), analogous to the coupon collector.

Answer

20.11208767\boxed{20.11208767}
Source code

Code

Each problem page includes the exact C++ and Python source files from the local archive.

C++ project_euler/problem_644/solution.cpp 
#include <iostream>

// Reference executable for problem_644.
// The mathematical derivation is documented in solution.md and solution.tex.
static const char* ANSWER = "20.11208767";

int main() {
    std::cout << ANSWER << '\n';
    return 0;
}