Problem 70. Parking
We have 10 parking spaces lined up from left to right. We also have 10 drivers, each with a favourite parking space (possibly multiple drivers for the same space). Drivers enter from the left in order. If a driver’s favourite parking space is available, they park there. Otherwise, they park in the first empty space to the right of their favourite spot. If they can’t find a spot using this method, they leave.
How many arrangements are there for favourite parking spaces that allow all drivers to park? (An arrangement is a sequence of 10 numbers \(a_1\) to \(a_{10}\), where \(a_i\) is the favourite parking space of the driver who enters i-th.)
The answer is \(11^9\). In general, if there are \(n\) drivers and \(n\) parking spaces, the answer is \((n+1)^{n-1}\).
Let us modify the problem in the following way: We have \(n\) drivers as in the original problem, but we add one more parking space right after the last space. We arrange these \(n+1\) parking spaces in a circle, in the clockwise order. Each driver has a favourite parking space, and the drivers enter in order, each starting from their favourite parking space and moving clockwise around the circle until they find the first empty parking space and park there.
In this modified problem, everyone can park, and at the end one of the spaces will be empty. A favourite parking space assignment in the modified problem is a solution to the original problem if and only if the empty space in the modified problem is the \(n+1\)’th space.
In the modified problem, since each person has \(n+1\) options for their favourite parking space, there are \((n+1)^n\) arrangements. Also, due to symmetry, in the modified problem, the number of arrangements that leave each parking space empty in the end are equal. Thus, exactly \(1/(n+1)\) fraction of the arrangements are valid for the original problem. Therefore, the the solution to the original problem is \((n+1)^n/(n+1) = (n+1)^{n-1}\). For \(n=10\), this amounts to \(11^9\).