December 22nd, 2004, 2:20 am
Let P(n) be the expected number of passengers sitting in their correct seats, if there are n seats and passengers. We want P(100).P(1) = 1. With only one seat, GW has to pick the right one. With n seats, think of GW picking one person in line (including himself) at random. If he picks himself (1 chance in n) everyone gets their correct seat. If he picks the kth person in line (k = 2 to n), 2 people are in the wrong seats (GW and person k) and k - 2 (the ones between GW and person k) are in the correct seats. The problem is now identical to the original, except that there are only n - k seats and passengers and if the first passenger picks the "correct" seat (GW's) it doesn't count as correct so you get only n - k - 1 additional passengers in the right seats instead of n - k.Therefore, P(n) 1 (the chance GW picks his own seat) plus 1/n (for each possible k) times the sum of k - 2 + P(n - k) - 1/(n - k + 1) from k = 2 to n. This makes P(n) approximately equal to n - (e - 1)*ln(n), or 92 for n = 100. I also agree the last passenger's chance is 1/2. Let Q(n) be the chance the last passenger gets her own seat if there are n seats and passengers. Q(2) is obviously 0.5. Assume Q(k) = 0.5 for k = 2 to n - 1. There are three possible things GW can do: pick his own seat (probability = 1/n, now the chance the last passenger gets his own seat is 1), pick the last passenger's seat (probability = 1/n, now the chance the last passenger gets his own seat is 0) and pick any other seat (probability (n-2)/n, now the chance the last passenger gets his own seat is 0.5). This clearly averages to 0.5.
Last edited by
Aaron on December 21st, 2004, 11:00 pm, edited 1 time in total.