Problems

Filters
Clear Filters

1 problem found

2024 Paper 2 Q12
D: 1500.0 B: 1500.0
discrete probability distributions combinatorics summation formulas conditional probability independence counting arguments

In this question, you may use without proof the results \[ \sum_{i=1}^{n} i^2 = \tfrac{1}{6}n(n+1)(2n+1) \quad \text{and} \quad \sum_{i=1}^{n} i^3 = \tfrac{1}{4}n^2(n+1)^2. \] Throughout the question, \(n\) and \(k\) are integers with \(n \geqslant 3\) and \(k \geqslant 2\).

  1. In a game, \(k\) players, including Ada, are each given a random whole number from \(1\) to \(n\) (that is, for each player, each of these numbers is equally likely and assigned independently of all the others). A player wins the game if they are given a smaller number than all the other players, so there may be no winner in this game. Find an expression, in terms of \(n\), \(k\) and \(a\), for the probability that Ada is given number \(a\), where \(1 \leqslant a \leqslant n-1\), and all the other players are given larger numbers. Hence show that, if \(k = 4\), the probability that there is a winner in this game is \[ \frac{(n-1)^2}{n^2}\,. \]
  2. In a second game, \(k\) players, including Ada and Bob, are each given a random whole number from \(1\) to \(n\). A player wins the game if they are given a smaller number than all the other players or if they are given a larger number than all the other players, so it is possible for there to be zero, one or two winners in this game. Find an expression, in terms of \(n\), \(k\) and \(d\), for the probability that Ada is given number \(a\) and Bob is given number \(a + d + 1\), where \(1 \leqslant d \leqslant n-2\) and \(1 \leqslant a \leqslant n - d - 1\), and all the other players are given numbers greater than \(a\) and less than \(a + d + 1\). Hence show that, if \(k = 4\), the probability that there are two winners in this game is \[ \frac{(n-2)(n-1)^2}{n^3}\,. \] If \(k = 4\), what is the minimum value of \(n\) for which there are more likely to be exactly two winners than exactly one winner in this game?

Solution:

  1. Suppose Ada is given \(a\), then she wins if the other \(k-1\) players all get a number between \(a+1\) and \(n\). Since each of these choices are independent, this occurs with probability: \begin{align*} && \mathbb{P}(\text{Ada wins with }a) &= \left ( \frac{n-a}{n} \right)^{k-1} \\ \\ && \mathbb{P}(\text{Ada wins}) &= \sum_{a=1}^{n-1} \mathbb{P}(\text{Ada wins with }a) \mathbb{P}(\text{Ada has }a) \\ &&&= \sum_{a=1}^{n-1}\frac{1}{n}\left ( \frac{n-a}{n} \right)^{3}\\ &&&= \frac{1}{n^4} \sum_{a=1}^{n-1} (n-a)^3 \\ &&&= \frac{1}{n^4} \sum_{a=1}^{n-1} a^3 \\ &&&= \frac{1}{n^4} \tfrac14(n-1)^2n^2 \\ &&&= \frac{(n-1)^2}{4n^2} \end{align*} Since each the game is symmetric, each player is equally likely to win, therefore the probability anyone wins is \(\displaystyle \frac{(n-1)^2}{n^2}\)
  2. The probability that Ada gets \(a\), Bob gets \(a+d+1\) and the other players are in between is \begin{align*} && \mathbb{P}(\text{event}) &= \mathbb{P}(\text{Ada gets }a) \mathbb{P}(\text{Bob gets }a+d+1) \mathbb{P}(\text{everyone else between}) \\ &&&= \frac1{n^2} \cdot \left ( \frac{d}{n} \right) ^{k-2} \end{align*} Therefore the probability that Ada and Bob jointly win is \begin{align*} && \mathbb{P}(\text{Ada and Bob win}) &= \sum_{d=1}^{n-2} \sum_{a=1}^{n-d-1} \frac{1}{n^4} d^2 \\ &&&= \frac{1}{n^4} \sum_{d=1}^{n-2} (n-1-d) d^2 \\ &&&= \frac{n-1}{n^4} \frac{(n-2)(n-1)(2n-3)}{6} - \frac{1}{n^4} \frac{(n-2)^2(n-1)^2}{4} \\ &&&= \frac{(n-1)^2(n-2)}{12n^4} \left ( 2(2n-3)-3(n-2) \right) \\ &&&= \frac{(n-1)^2(n-2)}{12n^3} \\ \end{align*} There are \(4\) players so there are \(4\) ways to choose the lowest player and \(3\) remaining ways to choose the highest, so we get \(\displaystyle \frac{(n-2)(n-1)^2}{n^3}\) probability of a winner happening. The probability of there being a highest winner is the same as the probability of there being a lowest winner (both \(\frac{(n-1)^2}{n^2}\)) and the probability of there being exactly one winner is therefore \begin{align*} && P_1 &= P_{\geq1}-P_2+P_{\geq1}-P_2 \\ \end{align*} this is less than \(P_2\) iff \begin{align*} && P_{\geq1}+P_{\geq1}-2P_2 &< P_2 \\ \Leftrightarrow && 2P_{\geq 1} & < 3P_2 \\ \Leftrightarrow && \frac{2(n-1)^2}{n^2} &< \frac{3(n-1)^2(n-2)}{n^3} \\ \Leftrightarrow && 2n&<3(n-2) \\ \Leftrightarrow && 6 &< n \end{align*} So \(n = 7\)

View