Airplane Seat Assignment Probability

We can solve it through a logical reasoning approach. First, let’s consider a few simple scenarios:

  • If n = 1, the only passenger will definitely sit in their own seat because there is only one seat, so the probability is 1.
  • If n = 2, the first passenger has a 50% chance of taking the second passenger’s seat. If they don’t, then the second passenger will definitely get their own seat, so the probability is 0.5.

For n > 2, things get a bit more complicated, but we can derive a solution based on a recursive observation. After the first passenger takes a seat, one of two scenarios will occur:

  1. The first passenger takes their own seat. In this case, everyone will sit in their own seat, so the nth person will sit in their own seat for sure. The probability of this happening is 1/n.
  2. The first passenger takes someone else’s seat, let’s say the kth seat. Now the kth person has to choose a seat, but the problem is exactly the same as the original problem, just with n replaced with k. That’s because the kth person will now pick either the first seat or one of the remaining k - 1 seats, ignoring the seats from k + 1 to n because those seats can’t be picked.

Based on the two scenarios, the total probability that the nth person will get their seat is 1/n + (1/n) * P(k = 2) + (1/n) * P(k = 3) + ... + (1/n) * P(k = n). Notice how this is identical to the original problem? This is a form of recursion.

The recursive equation is P(n) = 1/n + (1/n) * (P(2) + P(3) + ... + P(n - 1)), with base cases P(1) = 1 and P(2) = 0.5. However, because P(2) = P(3) = P(4) = ... = P(n), the equation simplifies to P(n) = 1/n + (n - 1)/n * P(n), which simplifies further to P(n) = 1, which is incorrect.

The trick is to realize that the recursion stops when the kth person (where k is not n) picks either the first seat or their own seat. The situation is symmetric between these two seats because they’re the only seats that, if picked, will stop the recursion and determine the final result. So, no matter how many people are involved (n), the last person (the nth person) has a 0.5 (or 50%) chance of getting their seat.

Python solution:

1
2
3

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        return 1.0 if n == 1 else 0.5

This function simply returns 1.0 if n equals 1 (since there’s only one passenger and one seat) and 0.5 otherwise, which is the probability of the nth passenger getting their own seat when n > 1.