Ponder This

July 2025 - Solution

<< May July

July 2025 Challenge

July 2025 Solution:

The numerical solutions are:

L1=6.0507220
L2=100.96564

Bonus:

m=1.26278296766

This problem is better known as "Rényi's Parking Problem" which deals with cars parking randomally along the road. When the cars are of unit length 1 and we're interested in the mean number of cars that will be able to park on an interval of length x, we have the following recursive formula:

M\left(x\right)=\begin{cases} 0 & 0\le x<1\\ 1 & x=1\\ 1+\frac{2}{x-1}\int_{0}^{x-1}M\left(t\right)dt & x>1 \end{cases}

This formula can be obtained in the following (rather informal) manner: Consider an interval of length x+1, and put a car on t (0\le t\le x), with the effect of splitting the interval into two smaller intervals of lengths t and x-t. The expected number of cars on the interval (0,x+1) in this case is M\left(t\right)+1+M\left(x-t\right) (since we also count the car already placed)

And now, using The symmetry of M(t) and M(x-t) we obtain M\left(x+1\right)=\frac{1}{x}\int_{0}^{x}\left[M\left(t\right)+1+M\left(x-t\right)\right]dt =1+\frac{2}{x}\int_{0}^{x}M\left(t\right)dt

There are several methods to numerically compute this integral. One nice approach described in "Numerical Solution of Some Classical Differential-Difference Equations" computes a power series representation for M in the interval [N,N+1] based on a power series representation for the previous integral. Implementing this approach yields an extremely fast and accurate algorithm for directly computing FD and a simple binary search algorithm (based on FD's monotonicity in the relevant domain) yields

A common answer to the bonus was 1.337617\ldots, which is \frac{1}{C_r} where C_r is Rényi's Parking Constant, C_r=\lim_{x\to\infty}\frac{M(x)} {x}. This is due to an interpretation of the bonus question as requesting the **mean** distance between two swallows. To compute it, first note the the distance between two consecutive swallows is equal to half the first swallow + half the second one + the empty space between them. So if we compute the mean empty space + 1, we obtain the requested result. The mean total empty space for a wire of length x is x-M(x), and dividing by the number of swallows yields the result 1+\frac{x-M(x)}{M(x)}=\frac{x}{M(x)} which, taken to the limit, is indeed \frac{1}{C_r}.

The intended meaning of the bonus was to find the median, not the mean. This can be done via a Monte Carlo simulation.