HMMT 二月 2012 · COMB 赛 · 第 9 题

英文解析

9. A parking lot consists of 2012 parking spots equally spaced in a line, numbered 1 through 2012. Oneby one, 2012 cars park in these spots under the following procedure: the first car picks from the 2012
   spots uniformly randomly, and each following car picks uniformly randomly among all possible choiceswhich maximize the minimal distance from an already parked car. What is the probability that thelast car to park must choose spot 1?
   Answer: We see that for 1 to be the last spot, 2 must be picked first (with probability 1
   2062300
   ), after which spot n is picked. Then, cars from 3 to n − 1 will be picked until there are only gaps 1
   of 1 or 2 remaining. At this point, each of the remaining spots (including spot 1) is picked uniformlynat random, so the probability that spot 1 is chosen last here will be the reciprocal of the number ofremaining slots.
   Let f ( n ) denote the number of empty spots that will be left if cars park in n + 2 consecutive spotswhose ends are occupied, under the same conditions, except that the process stops when a car isforced to park immediately next to a car. We want to find the value of f (2009). Given the gapn − 1 n − 1
   of n cars, after placing a car, there are gaps of f ( ⌊ ⌋ ) and f ( ⌈ ⌉ ) remaining. Thus, f ( n ) =
   2 2
   n − 1 n − 1
   f ( ⌊ ⌋ ) + f ( ⌈ ⌉ ). With the base cases f (1) = 1 , f (2) = 2, we can determine with induction that
   2 2
   {
   n − 1 n n 3
   x − 2 + 1 if 2 ≤ x ≤ · 2 − 2 ,
   f ( x ) =2
   n 3 n n
   2 if · 2 − 1 ≤ x ≤ 2 · 2 − 1 .
   1 1 12
   Thus, f (2009) = 1024, so the total probability is · = .
   2012 1024+1 2062300