Prob of 100th person sitting in 100th seat ....

Question :

A line of 100 airline passengers is waiting to board a plane. they each hold a ticket to one of the 100 seats on that flight. (for convenience, let's say that the nth passenger in line has a ticket for the seat number n.)

Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. all of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. if it is occupied, they will then find a free seat to sit in, at random.
What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?

Solution :

There are two ways of solving the problem..

Method 1 :

The prob of 100th person to sit in 100th seat = 1 - ( the prob of one of 1-99 sitting in the 100th desk)

= 1 - ( prob of 1st person sitting in 100th desk + prob of 2nd person sitting in 100th desk + … + prob of 99th person sitting in 100th desk)

= 1 - [ (1/100) + ( (1/100) * (1/99) ) + ( 1/100 + (1/100 + (1/100 * 1/99) ) * (1/98) + ….. ]

= 1 - [ This turns out to be 1/2 ]

= 1 - [1/2] = 1/2 .

Note for method 1 :

The prob of 1st person sitting in 100th desk = 1/100 ( Since he is crazy he can pick up any seat at random )

The prob of 2nd person sitting in 100th desk = combined prob of 1st person sitting in 2nd seat and 2nd person sitting @ 100th seat = (1/100 * 1/99)

The prob of 3rd person sitting in 100th desk = combined prob of 1st / 2nd person sitting in seat 3 and 3rd person sitting @ 100th seat = ( 1/100 + (1/100 + (1/100 * 1/99) ) ) * 1/98 …


Method 2 :


A much more elegant way of solving the same problem…

The question is for 100 passengers.

If there is only one passenger.

P(1) = 1

If there are 2 passengers

P(2) = Pass1 gets seat 1 = 1/2

If there are 3 passengers

P(3) = Pass1 gets seat 1 + (Pass1 gets seat 2 and P(2))

= 1/3 + 1/3 (P(2)) = 1/3 (1 +P(2)) = 1/2 (1 + 1/2) = 1/2

(after pass1 gets seat 2, pass2 only have 2 seats left where 1 now becomes his right seat, so it is a P(2) problem).


If there are 4 passengers

P(4) = Pass1 gets seat 1 + (Pass1 gets seat 2 and P(3)) + (Pass1 gets seat 3 and P(2))

= 1/4 + 1/4 (P(3)) + 1/4 (P(2)) = 1/4 (1 + P(2) + P(3)) = 1/4 (2) = 1/2


(after pass1 gets seat 2, pass2 has only 3 seats left where 1 now becomes his right seat, so it is a P(3) problem).

after pass1 gets seat 3, pass2 will take seat2. pass3 has only 2 seats left where 1 now becomes his right seat, so it is a P(2) problem).


It can deduced that if there are n passengers,

P(n) = 1/n (1 + P(2) + P(3) + ...P(n-1))

= 1/n (1 + 1/2 + ...+1/2) = 1/n ( 1+ (n-2)/2) = 1/n (n/2) = 1/2



So, I also think it is 1/2