Problems

A train has \(n\) seats, where \(n \geqslant 2\). For a particular journey, all \(n\) seats have been sold, and each of the \(n\) passengers has been allocated a seat. The passengers arrive one at a time and are labelled \(T_1, \ldots, T_n\) according to the order in which they arrive: \(T_1\) arrives first and \(T_n\) arrives last. The seat allocated to \(T_r\) (\(r = 1, \ldots, n\)) is labelled \(S_r\). Passenger \(T_1\) ignores their allocation and decides to choose a seat at random (each of the \(n\) seats being equally likely). However, for each \(r \geqslant 2\), passenger \(T_r\) sits in \(S_r\) if it is available or, if \(S_r\) is not available, chooses from the available seats at random.

1. Let \(P_n\) be the probability that, in a train with \(n\) seats, \(T_n\) sits in \(S_n\). Write down the value of \(P_2\) and find the value of \(P_3\).
2. Explain why, for \(k = 2, 3, \ldots, n-1\), \[ \mathrm{P}\bigl(T_n \text{ sits in } S_n \mid T_1 \text{ sits in } S_k\bigr) = P_{n-k+1}, \] and deduce that, for \(n \geqslant 3\), \[ P_n = \frac{1}{n}\Biggl(1 + \sum_{r=2}^{n-1} P_r\Biggr). \]
3. Give the value of \(P_n\) in its simplest form and prove your result by induction.
4. Let \(Q_n\) be the probability that, in a train with \(n\) seats, \(T_{n-1}\) sits in \(S_{n-1}\). Determine \(Q_n\) for \(n \geqslant 2\).