1
$\begingroup$

You are going to a concert. The road to the concert has 100 car parking spaces arranged in a straight line. The spaces are numbered from 1 to 100, where space 1 is in the beginning of your journey and space 100 is right at the concert's gate. Obviously spaces that are closer to the gate are more likely to be taken. The probability that a parking space numbered $n$ is taken is $n/100$. If you have missed an empty parking space then you cannot return to it and if you didn't find a park then you miss out on the concert. What should be your strategy in finding^ an empty parking space that is as close to the gate as possible?

^ Assume that "finding a space" means that you can guarantee that it will be empty with probability 99.9% or more. For example the probability that space 1 is empty is 99%, so it alone doesn't meet the rule. However, the probability that space 1 or space 2 is empty is $0.99+0.98-0.99*0.98 = 0.9998 > 99.9\%$, so you can guarantee yourself a park in one of these spots.

$\endgroup$
5
  • 1
    $\begingroup$ I come across this puzzle frequently in my daily life. Just the other day I went to botanic gardens and there was a long road for cars to park. I though I will be greedy and go all the way to the gate of the gardens. Surely there will be a park there somewhere? Nope, as I approached the gate, the number of empty parks diminished exponentially. So I found no park and had to drive all the way back for one. As I walked to the gate, there were 3 empty parks right there! I kept this puzzle simple with linear probability decay and no return trip, but the more general version also interests me. $\endgroup$ Aug 24 '21 at 14:28
  • $\begingroup$ The 99.9% rule doesn't make sense as then you go straight to the furthest spot as it is the only one with >99.9% probability of being empty. I put in an edit removing that rule $\endgroup$
    – Ankit
    Aug 24 '21 at 14:31
  • $\begingroup$ @Ankit so I tried to explain what I mean by that rule in the new edit. Otherwise, you can't really guarantee to find any spots as there is a tiny chance that ALL spaces are taken. $\endgroup$ Aug 24 '21 at 14:43
  • $\begingroup$ This looks a little bit like the Secretary Problem but as loopy walt's answer shows, this is actually much easier. $\endgroup$ Aug 24 '21 at 15:04
  • $\begingroup$ @JaapScherphuis yeah I was aiming for something like the secretary problem with a twist, but it turned out less interesting. $\endgroup$ Aug 24 '21 at 15:12
6
$\begingroup$

You should

pass the first 64 and then take the first one that is free.

because

it is at term 36 that 100% x 99% x 98% x ... is less than 1/1000 for the first time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.