The Computer Laboratory

Practice Paper 3 Question 13

\(n\) passengers board a plane with \(n\) seats. Each passenger has an assigned seat. The first passenger forgets and takes a seat at random. Every subsequent passenger sits in their assigned seat unless it is already taken, at which point they take a random seat. What is the probability (in terms of \(n\)) that:

  1. Every passenger sits in the correct seat?
  2. At least one passenger sits in the correct seat?
  3. Exactly one passenger sits in the correct seat?

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  1. What is the probability of not getting a six in ten rolls of a dice?
  2. Evaluate \(\sum_{k=10}^{50}k.\)
  3. Evaluate \(\prod_{k=1}^{50}\frac{k}{k+1}.\)

Hints

  • Hint 1
    (Part ii) Would it be easier to calculate the probability that at least one passenger sits in the correct seat indirectly?
  • Hint 2
    (Part ii) Try using the probability that no passenger sits in the correct seat.
  • Hint 3
    (Part iii) If the fourth passenger is the only one in the correct seat, where must the first and second passengers sit?
  • Hint 4
    (Part iii) Where must the third passenger sit if the fourth passenger is to be the only one in the correct seat? What about any subsequent passengers?
  • Hint 5
    (Part iii) Try to find the probability that only one passenger sits in their assigned seat by finding the probability that only the \(i^{th}\) passenger is sitting in their assigned seat.

Solution

If the first passenger sits in the correct seat, then every other passenger will be able to take their assigned seat. Hence the probability that all the passengers take their assigned seat is \(\frac{1}{n}.\)

For every passenger to sit in the wrong seat, each passenger must sit in the seat of the next one to board. The probability of this is \(\frac{1}{n} \cdot \frac{1}{n-1} \cdot \ldots \cdot \frac{1}{1}\) \(=\prod_{i=1}^{n}\frac{1}{i}\) \(= \frac{1}{n!}.\) Therefore we deduce that the probability of at least one passenger sitting in the correct seat is \(1-\frac{1}{n!}.\)

We will first calculate the probability that only the \(k^{th}\) passenger is sitting in the correct seat. For this to happen, every passenger except the \(k^{th}\) and \((k-1)^{th}\) one must sit in the seat of the next one to board. The \((k-1)^{th}\) passenger must sit in the seat of the \((k+1)^{th}\) one unless there are only \(k\) passengers; in this case they must sit in the seat of the first passenger to board.

Hence every passenger but the \(k^{th}\) has a \(1/i\) chance of choosing the required seat, where \(i\) is the number of seats left available. Let \(j\) be the number of seats left when the \(k^{th}\) passenger boards. Therefore, the probability that the \(k^{th}\) passenger is the only one in the correct seat is \(\frac{1}{n} \cdot \frac{1}{n-1} \cdot \ldots \cdot \frac{j}{j} \cdot \ldots \cdot \frac{1}{2} \cdot \frac{1}{1} = \frac{j}{n!}.\)

We sum over all possible values of \(j\) up to \(n-1.\) Note that we exclude \(j=n\) because that implies the first passenger is sitting in the correct seat, in which case everyone is sitting correctly. \[ \sum_{j=1}^{n-1}\frac{j}{n!} = \frac{n(n-1)}{2n!} = \frac{1}{2(n-2)!}. \]

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.footasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.