Solve drunk-passenger probability and simulate outcome

A single-aisle plane has $n=100$ passengers numbered 1 through 100 and 100 assigned seats numbered 1 through 100. Passenger 1 is intoxicated and picks a seat according to a uniform distribution over the 100 seats. For every later passenger $i$ ($2 \le i \le 100$), if seat $i$ is free they take it; otherwise they pick uniformly at random among the remaining empty seats. 1) Find a closed-form formula for the probability that passenger 100 ends up in seat 100. 2) Extend the result to arbitrary $n \ge 2$ and prove it, using a short induction or invariant argument. 3) Write a Monte Carlo simulator in R or Python to estimate this probability for $n=100$ with at least 1e6 trials; report the estimate, its standard error, and a 95% confidence interval, and check that it matches the theoretical value within 0.01. 4) Compare the time and space complexity of a naive simulation with an optimized method that tracks only the two boundary seats.

Overview: This problem tests probabilistic reasoning and intuition for stochastic processes, including invariant arguments, closed-form derivations, Monte Carlo statistical estimation, and algorithmic time and space complexity analysis.