100 Airlines passenger are standing in a queue to board a plane. They each hold a ticket to one of the 100 seats in that flight (n’th passenger in the queue hold the ticket for seat # n). First passenger is drunk, and he picks a random seat and sit on it.
All the other passengers go inside one-by-one and occupy seats according to the below logic
- Each passenger will occupy its own seat, if its seat is not already occupied by another.
- If its seat is occupied by another passenger, He will pick a random seat from the available (vacant) seats.
If you are the 100th passenger, what is the probability that you end up in your allotted seat (seat no. 100)?
Consider Seat no. 1 and Seat no. 100. For passengers between 1 & 99, Both the below outcomes are equally probable
ReplyDelete* Seat no. 1 is occupied before Seat no. 100
* Seat no. 100 is occupied before Seat no. 1
Because no passenger target to sit on any of those seats (Passenger-1 is drunk and we are not considering Passenger-100).
If drunk passenger take Seat no. k, then all the passengers from 2 to k-1 till take their respective seats (because they are vacant). The k’th passenger can either take Seat-1 or any other seat.
If he takes seat no. 1 then all the passengers after k will sit on their respective seats.
If he takes any random seat, say p (p>k), then all the passengers from k+1 to p-1 will sit on their allotted seats.
So we can treat passenger k as the new drunk passenger whose allotted seat is seat no.1.
We can define P(n) as a relative equation. P(n) – Solution to the puzzle with n passengers
P(n) = 1/n + P(n-1)/n + P(n-2)/n + …… + P(2)/n
P(2) = 1/2
P(3) = 1/3 + (1/2)/3 = 1/3 + 1/6 = 1/2
P(4) = 1/4 + 1/8 + 1/8 = 1/2
Hence, The answer to 100 passengers is 1/2 or 0.5