Solution
The Parking Constant
Show the problem again
Cars of length 1 arrive one at a time at a kerb of length L. Each car parks in a position chosen uniformly at random among all positions where it fits without overlapping a previously parked car (and stays inside the kerb). This continues until no gap of length at least 1 remains. As L → ∞, the expected fraction of the kerb covered by cars tends to a constant. Give that constant rounded to 3 decimal places.
Worked solution
The answer is about 0.748 (Rényi's parking constant, 0.74759...). Let M(x) be the expected number of cars that end up in an empty gap of length x. The first car lands with its left end uniform in [0, x − 1], leaving independent gaps of lengths t and x − 1 − t, so for x ≥ 1 M(x) = 1 + (2/(x − 1)) ∫₀^{x−1} M(t) dt, with M(x) = 0 for x < 1. Rényi solved this delay integral equation with Laplace transforms and showed M(x)/x → c, where c = ∫₀^∞ exp(−2 ∫₀^t (1 − e^(−u))/u du) dt ≈ 0.747598. Numerical evaluation of this integral and a direct simulation (streets of length 2000, thousands of runs, giving 0.7475 after the expected O(1/L) edge correction) agree. Random sequential parking wastes about a quarter of the kerb, compared with zero for careful packing.
Source: Rényi's parking problem (Alfréd Rényi, 1958). Statement written for AxiomIQ.