Compute probability last passenger gets own seat

There are 100 passengers boarding a plane with 100 seats, numbered 1 to 100. Passenger i (for 1 ≤ i ≤ 100) has a ticket for seat i.

The boarding process is as follows:

1. Passenger 1 is drunk and ignores the seat assignment. They choose one of the 100 seats uniformly at random and sit there.
2. For each subsequent passenger k from 2 to 100:
   • If seat k (their assigned seat) is still empty, they sit in seat k.
   • Otherwise (if their assigned seat is already occupied), they choose uniformly at random from all the remaining empty seats and sit in one of those.

You are passenger 100. What is the probability that you end up sitting in your own assigned seat (seat 100)?

Give the final probability as a simplified fraction or decimal.

Probability the Last Passenger Gets Their Own Seat

There are n passengers boarding a plane with n seats, numbered 1 to n. Passenger i holds a ticket for seat i.

Boarding proceeds in order:

1. Passenger 1 is drunk and ignores the seat assignment, choosing one of the n seats uniformly at random.
2. For each subsequent passenger k (from 2 to n):
   • If their assigned seat k is still empty, they sit in seat k.
   • Otherwise, they choose uniformly at random among all remaining empty seats.

Return the probability that the last passenger (passenger n) ends up in their own assigned seat (seat n), as a floating-point number.

This is the classic "lost boarding pass" / Green Book puzzle. Implement it as an exact computation (not a Monte-Carlo estimate) so the answer is deterministic.

Examples:

• n = 1 -> 1.0 (the only passenger must sit in seat 1)
• n = 2 -> 0.5
• n = 100 -> 0.5

Hint about the math: Let p(m) be the probability for an m-passenger instance. The first disruptor picks uniformly among m seats. With probability 1/m they take seat 1 (last passenger surely succeeds); with probability 1/m they take seat m (last passenger surely fails); otherwise, for a seat j with 2 <= j <= m-1, passenger j becomes the new disruptor over m - j + 1 relevant seats, contributing p(m - j + 1).

Constraints

• 0 <= n <= 100000 (use exact rational arithmetic or the closed form to stay deterministic)
• Return a float; for n >= 2 the exact answer is 0.5
• n = 1 returns 1.0; n <= 0 returns 0.0 by convention

Hints

1. Think recursively about who the current 'disruptor' is. After passenger 1 sits randomly, every later passenger either finds their own seat free or becomes a new disruptor.
2. The outcome for the last passenger is decided the moment a disruptor sits in either seat 1 (success) or seat n (failure) — by symmetry these two are equally likely.
3. Set up p(1) = 1 and p(m) = 1/m + sum over middle seats of (1/m) * p(m - j + 1), then notice the result collapses to 1/2 for every m >= 2.