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)?
1 comment:
Consider Seat no. 1 and Seat no. 100. For passengers between 1 & 99, Both the below outcomes are equally probable
* 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
Post a Comment