What is the probability that everyone's actual seat number and their assigned seat number differ by at most 1? That is, no one sits more than 1 seat away from their assigned seat.
Solution
Zeke's solution in the comment is correct.
Tuesday, October 27, 2009
Passengers Boarding Airplane, Part Deux
2009 passengers are waiting in a line to board an airplane with 2009 seats. The seats are numbered from 1 to 2009. Each passenger has a boarding pass that has his/her seat number on it. However, these passengers are oblivious to their boarding pass and choose their seats at random, each with a uniform probability from the available empty seats.
What is the probability that everyone's actual seat number and their assigned seat number differ by at most 1? That is, no one sits more than 1 seat away from their assigned seat.
Zeke's solution in the comment is correct.
What is the probability that everyone's actual seat number and their assigned seat number differ by at most 1? That is, no one sits more than 1 seat away from their assigned seat.
Zeke's solution in the comment is correct.
Subscribe to:
Post Comments (Atom)
lol nice.
ReplyDeleteLet f(n) be the number of permutations where among n passengers no one sits more than 1 seat away from their assigned seat. We can obtain f(n+1) as follows. Observe that the (n+1)th passenger must be in either his seat or the nth seat. If he sits in his seat then all passengers in front of him must sit in a valid configuration - there are f(n) of these. If he does not sit in his seat, then he must sit in the nth seat, and the nth passenger must sit in the (n+1)th seat. (Note that it must be the nth passenger in the (n+1)th). Now, all passengers before the (n+1)th passenger must be in a valid configuration - there are f(n-1) of these.
Hence, f(n+1) = f(n) + f(n-1). Note that f(1) = 1, f(2) = 2. This is the Fibonacci series (fudging indices but whatever)
So, the probability is f(n)/(n!). For n=2009, that's pretty much 0. (as was apparent from the start)