"$n$ music lovers have reserved seats in a theater containing a total of $n+k$ seats ($k$ seats are unassigned). The first person who enters the theater, however, lost his seat assignment and chooses a seat at random. Subsequently, people enter the theater one at a time and sit in their assigned seat unless it is already occupied. If it is, they choose a seat at random from the remaining empty seats. What is the probability that person $n$, the last person to enter the theater, finds their seat already occupied?"
I could do this problem for small specific values of $n$ and $k$ but as they grow the expressions seem to get really messy really quick with no discernible pattern. How would one solve this problem?
Best Answer
Let $N=n+k$. I claim the probability that person $i$'s seat is taken already when she walks into the room is $\frac{1}{N-i+2}$, if $i>1$. We can prove this by induction. Indeed if $1<j<i$ then, by induction, the probability that $j$ chooses a seat at random is $\frac{1}{N-j+2}$, so the probably that somebody takes $i$'s seat is
$$\frac{1}{N} + \sum_{1<j<i} \frac{1}{N-j+2}\frac{1}{N-(j-1)} = \frac{1}{N} + \sum_{1<j<i} \left(\frac{1}{N-(j-1)}-\frac{1}{N-(j-2)}\right) = \frac{1}{N-i+2}.$$
(The probability that $j$ takes seat $i$, if $j$ chooses a seat at random and nobody has yet taken seat $i$, is $1/(N-(j-1)$.)
Taking $i=n$, you get $1/(k+2)$.
There is a second, admittedly much nicer way to get this answer. Notice that as soon as anybody chooses any of the seats $1,n,n+1,\ldots,n+k$, the fate of person $n$ is sealed, because every subsequent person takes her own seat. Clearly each of the seats $1,n,\ldots,n+k$ is equally likely to be taken first, so the probability that seat $n$ is taken first is $1/(k+2)$.