## 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.

#### Solution

Zeke's solution in the comment is correct.

#### 1 comment:

1. lol nice.

Let 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)