The seats in a lecture hall are ordered 1-100. The students waiting to get in are also numbered 1-100, and they are allowed to enter the lecture hall one-by-one in order. They pick a seat according to the following rule. If the seat that matches their number is available, they sit in that seat. If it's not available, they choose a random seat. The exception is person #1, who sits in a random seat. What is the probability that person #100 will sit in seat #100?

Solution

Acting it out—in your mind or on paper—is a good approach. Imagine that the first person randomly chooses seat #95. Then the next 94 people will sit in the seat numbers that match their number. Person #95 will choose a seat randomly. If he chooses seat #1, the rest of the people (including person #100) will sit in the correct seats. If he chooses #100, then person #100 will obviously not sit in that seat. If he chooses 96-99, then this whole process repeats until one of the people chooses seat #1 or seat #100. That means that there is a 50% chance that person #100 will sit in seat #100.

Menu