Airplane Seat Assignment Probability

Problem Description

n passengers board an airplane with exactly n seats. The first passenger has lost the ticket and picks a seat randomly. For every subsequent passenger, they will take their own seat if available, otherwise they pick a seat at random from what remains. Determine the probability that the nth passenger gets to sit in their own seat.

Key Insights

• The problem has a surprising constant probability for any n >= 2.
• Instead of simulating the whole process, a pattern (or recurrence) can be observed.
• The probability turns out to be exactly 1 for n = 1, and 0.5 for any n >= 2.
• The key insight is that only the fate of the first and the nth seat matters as the randomness propagates.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

The first passenger picks a random seat. Three outcomes occur:

1. He picks his own seat: All subsequent passengers, including the nth, will sit in their assigned seats.
2. He picks the nth passenger's seat: The nth passenger loses his seat.
3. He picks a seat that is neither his own nor the nth’s. In the third case, the new "problem" reduces to a smaller instance with the same structure. By analyzing the recursive events, it can be shown that the probability is reduced to a 50-50 chance for the nth passenger if n ≥ 2. Thus, if n == 1, the probability is 1.0; otherwise, it is 0.5.

Algorithm:
Check if n is 1. If yes, return 1.0. Otherwise, return 0.5.
Data Structures:
No complex data structures are needed; a simple conditional check works.

Code Solutions