Airplane Seat Assignment Probability - Solution & Explanation

The problem can be broken down using dynamic programming (DP). Let's denote dp[i] as the probability that the i^th person gets his own seat. The first passenger (1st person) picking a seat will influence the probability calculation.

Base Cases:

• dp[1] = 1 because the 1st person will always get his seat.
• dp[2] = 0.5 because the only two choices for the 1st person are seat 1 (resulting in seat 2 for passenger 2) or seat 2 (resulting in probability 0 for passenger 2).

Recursive Case:

• When i > 2, if seat 1 is chosen by the 1st person, person i has the same problem as person i-1. Hence, please observe that the convergence values become dp[i]=dp[i-1], as further passengers choosing other emtpy seats propagate the recurrence.

This implementation makes use of the observed pattern that for n > 1, the probability stabilizes at 0.5 across large values of n. Essentially, we calculate the probability based on these conditions, speeding computation.

Through mathematical examination of the seat assignment problem, note that each passenger faces identical probability choices, independent of the initial convolutions by the first passenger. The nth person getting their seat can derive from recursive seated events indicating a general stasis at 0.5 beyond n=2.

This solution is formulated from recognizing repeated statistical expectation among larger sample sizes, affirming 0.5 likeliness past binary selection.

Let f(n) represent the probability that the nth passenger will sit in their own seat when there are n passengers boarding. Consider from the simplest case:

When n=1, there is only 1 passenger and 1 seat, so the first passenger can only sit in the first seat, f(1)=1;

When n=2, there are 2 seats, each seat has a probability of 0.5 to be chosen by the first passenger. After the first passenger chooses a seat, the second passenger can only choose the remaining seat, so the second passenger has a probability of 0.5 to sit in their own seat, f(2)=0.5.

When n>2, how to calculate the value of f(n)? Consider the seat chosen by the first passenger, there are three cases.

• The first passenger has a probability of \frac{1}{n} to choose the first seat, then all passengers can sit in their own seats, so the probability of the nth passenger sitting in their own seat is 1.0.

• The first passenger has a probability of \frac{1}{n} to choose the nth seat, then the second to the (n-1)th passengers can sit in their own seats, the nth passenger can only sit in the first seat, so the probability of the nth passenger sitting in their own seat is 0.0.

• The first passenger has a probability of \frac{n-2}{n} to choose the remaining seats, each seat has a probability of \frac{1}{n} to be chosen. Suppose the first passenger chooses the ith seat, where 2 \le i \le n-1, then the second to the (i-1)th passengers can sit in their own seats, the seats of the ith to the nth passengers are uncertain, the ith passenger will randomly choose from the remaining n-(i-1)=n-i+1 seats (including the first seat and the (i+1)th to the nth seats). Since the number of remaining passengers and seats is n-i+1, and 1 passenger will randomly choose a seat, the problem size is reduced from n to n-i+1.

Combining the above three cases, we can get the recursive formula of f(n):

$ \begin{aligned} f(n) &= \frac{1}{n} times 1.0 + \frac{1}{n} times 0.0 + \frac{1}{n} times sum_{i=2}^{n-1} f(n-i+1) \ &= \frac{1}{n}(1.0+sum_{i=2}^{n-1} f(n-i+1)) \end{aligned}

In the above recursive formula, there are n-2 values of i, since the number of values of i must be a non-negative integer, so the above recursive formula only holds when n-2 \ge 0 i.e., n \ge 2.

If you directly use the above recursive formula to calculate the value of f(n), the time complexity is O(n^2), which cannot pass all test cases, so it needs to be optimized.

Replace n with n-1 in the above recursive formula, you can get the recursive formula:

f(n-1) = \frac{1}{n-1}(1.0+sum_{i=2}^{n-2} f(n-i))

In the above recursive formula, there are n-3 values of i, and the above recursive formula only holds when n-3 \ge 0 i.e., n \ge 3.

When n \ge 3, the above two recursive formulas can be written as follows:

\begin{aligned} n times f(n) &= 1.0+sum_{i=2}^{n-1} f(n-i+1) \ (n-1) times f(n-1) &= 1.0+sum_{i=2}^{n-2} f(n-i) \end{aligned}

\begin{aligned} &~~~~~ n times f(n) - (n-1) times f(n-1) \ &= (1.0+sum_{i=2}^{n-1} f(n-i+1)) - (1.0+sum_{i=2}^{n-2} f(n-i)) \ &= sum_{i=2}^{n-1} f(n-i+1) - sum_{i=2}^{n-2} f(n-i) \ &= f(2)+f(3)+...+f(n-1) - (f(2)+f(3)+...+f(n-2)) \ &= f(n-1) \end{aligned}

\begin{aligned} n times f(n) &= n times f(n-1) \ f(n) &= f(n-1) \end{aligned}

Since we know that f(1)=1 and f(2)=0.5, therefore when n \ge 3, according to f(n) = f(n-1), we know that for any positive integer n, f(n)=0.5. And since f(2)=0.5, therefore when n \ge 2, for any positive integer n, f(n)=0.5.

From this, we can get the result of f(n):

f(n) = \begin{cases} 1.0, & n = 1 \ 0.5, & n \ge 2 \end{cases}

The time complexity of this solution is O(1), and the space complexity is O(1)$.