Solve drunk-passenger probability and simulate outcome

There are n=100 passengers labeled 1..100 and 100 assigned seats labeled 1..100 on a single-aisle plane. Passenger 1 is drunk and chooses a uniformly random seat among the 100. Each subsequent passenger i (2 ≤ i ≤ 100) sits in seat i if available; otherwise they choose uniformly at random from the remaining unoccupied seats. 1) Derive a closed-form expression for the probability that passenger 100 sits in seat 100. 2) Generalize and prove your result for arbitrary n ≥ 2, giving a brief inductive or invariant-based proof. 3) Implement a Monte Carlo simulator (R or Python) that estimates this probability for n=100 with at least 1e6 trials; report the estimate, standard error, and a 95% confidence interval, and verify it agrees with theory within 0.01. 4) Discuss the time and space complexity of a naive simulation versus an optimized approach that tracks only the two boundary seats.