Wednesday, February 16, 2011

Drunken Passanger

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:

Shashank Mani said...

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