2009 passengers are waiting in a line to board an airplane with 2009 seats. Each passenger has a boarding pass that has his/her seat number on it. The first passenger, however, was oblivious and chose a random seat to sit on.
For each subsequent passenger, he/she will try to sit on his/her assigned seat first. If that seat is taken by someone else, he/she will choose a random empty seat to sit on.
What is the probability that the last passenger would sit on his assigned seat?
Solution: http://dharmath.blogspot.com/2010/05/solution-passengers-boarding-airplane.html
Subscribe to:
Post Comments (Atom)
1:2008!
ReplyDeleterandom guess...
1/2
ReplyDeleteP_n = (1/n) * 1 + (1/n) * 0 + ((n-2)/n) * P_(n-1)
because there is 1/n chance that the first passenger will pick his seat, in which case the last passenger will get his; 1/n chance the first passenger will pick the last passenger's seat; in all other cases observe that we have a situation where there are (n-1) seats and the passenger is making a random choice among them. The difference in this case is that the 'right' seat is the one that the previous passenger making the random choice should sit in to allow everyone else to sit in their own seats. e.g. If the first passenger sat in the second's seat, the 'right' seat for the second passenger is the first's. Note that there is only one such seat.
Now, observe that P_2 = 1/2 since the first passenger can sit in either his spot or the second's spot with probability 1/2. We will now prove by induction that P_n = 1/2.
Assume P_n = 1/2. Then, P_(n+1) = 1/(n+1) + ((n-1)/(n+1)) * 1/2 = 1/2. Therefore, by induction P_n = 1/2 for all positive integers n. In particular, it's true for 2009.
oops. proof fail :P scratch that
ReplyDelete