Puzzle

N women stand in a queue to take seats in an auditorium. Seating is pre-assigned. However, the first woman is an absent-minded professor who chooses any of the N seats at random. Subsequent women in the queue behave as follows: if the seat assigned to her is available, she takes it. Otherwise, she chooses an unoccupied seat at random. What are the chances that the last woman in the queue shall get the seat assigned to her?

Source

From some compendium of Math competition problems.

Solution

The chances are one in two. Proof by induction. The base case, N = 2, is immediate. In general, the absent-minded professor might choose her assigned seat with probability 1/N, in which case the last woman surely gets her assigned seat. The absent-minded professor might choose the last woman's seat with probability 1/N, in which case the last woman definitely loses her seat. In each of the remaining N-2 cases, by induction, the chances of the last woman getting her assigned seat are one in two. Combining these cases, we see that the overall probability is .

© Copyright 2008—2018, Gurmeet Manku.