Park Your Car
Combinatorics, Probability; Difficulty: medium
Park your car
This week’s Riddler Classic is mainly an exercise in combinatorics. The Classic reproduced:
From Dave Moran comes a practical parking puzzle:
There’s a parking lot behind Dave’s office building with 10 spaces that are available on a first-come, first-serve basis. Those 10 spaces invariably fill by 8 a.m., and the parking lot quickly empties out at 5 p.m. sharp.
Every day, three of the 10 “early birds” who snagged spots before 8 a.m. leave at random times between 10 a.m. and 3 p.m. and do not return that day. Knowing that some early birds leave during that five-hour window, nine “stragglers” drive by the lot at random times between 10 a.m. and 3 p.m. If there’s an available spot, a straggler immediately parks in the spot and doesn’t leave until 5 p.m. If there’s no open spot, a straggler immediately drives away from the lot and parks somewhere else, and doesn’t return that day.
Suppose you are a straggler arriving at a random time between 10 a.m. and 3 p.m. What is the probability that you will get a spot in the lot?
*spoiler alert* solution and answer follow below
Solution
The uniform random selection of times in the five hour window might have you thinking about multiple integrals. Rest assured, that is not needed. This is really a combinatorics exercise. Let’s first explore the solution for the specific case in the Riddler. The following section discusses the general case.
Since the three early bird departures and the nine straggler arrivals (you and eight others) all occur randomly within the same time window, there are 12! = 479001600 equally likely ways to sequence the 12 events. (considering all 12 people distinguishable)
Let \(b_1, b_2, b_3 \) represent the early birds, \(s_1\) through \(s_8\) represents the eight other stragglers besides you, and \(S\) is you.
Only the following scenarios can result in you finding a spot:
- …bS…
- …bbsS…
- …bbbssS…
- …bbsbsS…
Here b represents any early bird, s any straggler and S is you.
Consider event sequences where your arrival event among the twelve events is:
- first: you are obviously not getting a parking spot.
- second or third : only the bS sequence allows you to snag a spot. There are 3 ways to pick the first early bird and 10! ways to pick the rest of the 10 spots. Total number of favorable sequences when your arrival is the second or third event is 3 X 10! (for each arrival slot)
- fourth or fifth: in addition to the bS sequence, you can also get a spot with a bbsS in the sequence. There are 3 ways to pick the two early birds and 2 ways to permute them, and 8 ways to pick the straggler before you and 8! ways to select the 8 stragglers after. Total = 6 X 8 X 8! (again, for each arrival slot)
- sixth through twelfth: In addition to the bS and bbsS sequences, it’s possible to get a spot with bbbssS or bbsbsS. Similar logic as before gives 6 X 8 X 7 X 6! ways for each of the two sequences for each arrival slot.
Adding it all up for when you end up in second through twelfth place in the 12 events, the total number of feasible sequences is: 140555520.
The required probability is then:
\begin{align*}
\frac{140555520}{479001600} \ \approx \ 0.2934
\end{align*}
29.34% is the required probability that you will get a spot.
The General Solution
It is possible to derive a simple recursive relationship for the probabilities that can be used for a different/larger number of early birds and or stragglers:
Let \(f(b,s,e)\) represent the probability of you finding a spot when there are \(b\) early birds, \(s\) other stragglers and \(e\) vacant spots (say due to already departed early birds). In the original question, we have been asked to find \( f(3,8,0) \).
Now we can condition on the first/next event which can either be:
- you arriving
- one of the \(s\) stragglers arriving
- one of the \(b\) early birds leaving
The probability of you getting a spot if your arrival is the first event is 0 if \(e = 0\) and \( \displaystyle \frac{1}{b + s + 1} \) for \(e>0\).
The probability of one of the other stragglers arriving first is \( \displaystyle \frac{s}{b + s + 1} \). And the probability of you getting a spot in this case is just \(f(b,s-1, max(e-1,0)) \) since an arriving straggler will take a spot \(e\) if it’s available.
Finally one of the early birds leaving has a probability \( \displaystyle \frac{b}{b + s + 1}\) and your probability of finding a spot is \(f(b-1,s, e+1) \). Note that an early bird leaving results in one more vacant spot available, hence the \(e+1\)
This gives us the recursive relationship and boundary values needed to compute any \(f(b,s,e)\) :
\begin{align*}
f(b,s,e) &= \frac{1}{b+s+1}min(1,e) \ + \ \frac{s}{b+s+1}f(b,s-1,max(0,e-1)) + \frac{b}{b+s+1}f(b-1,s,e+1) \\ \\
f(b,0,0) &= \frac{b}{b+1} \quad \quad \ \ \ \ \ \ \textit{(probability of not being first when no stragglers and vacanct spots) } \\ \\
f(b,0,e) &= 1 \quad \left \{ e> 0 \right \} \quad \textit{(you’re guaranteed a spot when there is a vacant spot and no stragglers)} \\
\end{align*}
A simple python script implementing this is included below.
Running this for a range of values gives the 3D plot below. There is a steep drop off in your chances when the first few stragglers enter the fray.
from functools import cache
@cache
def prob(b,s,e):
if s == 0 and e == 0:
return b/(b+1)
elif s == 0 and e != 0:
return 1
else :
return ((1/(s+b+1))*min(1,e) + (s/(s+b+1))*prob(max(0,b),s-1,max(0,e-1)) + (0 if b == 0 else (b/(s+b+1))*prob(b-1,s,e+1)))
print(prob(3,8,0))