Problems

Filters
Clear Filters

4 problems found

2021 Paper 2 Q11
D: 1500.0 B: 1500.0
conditional probability recurrence relation proof by induction combinatorics random seating problem discrete probability

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\).

View
2007 Paper 1 Q13
D: 1500.0 B: 1469.5
probability conditional probability combinatorics without replacement counting discrete probability

A bag contains eleven small discs, which are identical except that six of the discs are blank and five of the discs are numbered, using the numbers 1, 2, 3, 4 and 5. The bag is shaken, and four discs are taken one at a time without replacement. Calculate the probability that:

  1. all four discs taken are numbered;
  2. all four discs taken are numbered, given that the disc numbered ``3'' is taken first;
  3. exactly two numbered discs are taken, given that the disc numbered ``3'' is taken first;
  4. exactly two numbered discs are taken, given that the disc numbered ``3'' is taken;
  5. exactly two numbered discs are taken, given that a numbered disc is taken first;
  6. exactly two numbered discs are taken, given that a numbered disc is taken.

Solution: There are many ways to do the counting in each question, possibly the clearest way is to always consider the order in which discs are taken, although all methods should work equally well. For some examples Bayes rule also offers a fast solution.

  1. There are we are choose \(4\) objects in order from \(5\) (ie \({^5\P_4}\)) to obtain valid draws, this is out of a total of picking \(4\) objects from \(11\) (\({^{11}\P_4}\)). Ie the probability is: \(\displaystyle \frac{{^5\P_4}}{{^{11}\P_4}} = \frac{5! \cdot 7!}{11!} = \frac{1}{66}\) Alternatively, there are \(\binom{5}{4}\) ways to choose four numbered discs, out of \(\binom{11}{4}\) ways to choose four discs. ie \(\displaystyle \binom{5}{4} \Big / \binom{11}{4} = \frac{5 \cdot 4! \cdot 7!}{11!} = \frac{5 \cdot 4 \cdot 3 \cdot 2}{11 \cdot 10 \cdot 9 \cdot 8} = \frac1{66}\)
  2. \begin{align*} \mathbb{P}(\text{all four discs are numbered} | \text{first disc is 3}) &= \frac{\mathbb{P}(\text{all four discs are numbered and first disc is 3})}{\mathbb{P}( \text{first disc is 3})} \\ &= \frac{^4\P_3 \big / {^{11}\P_4}}{1/11} \\ &= 11\cdot \frac{4!}{1!} \Bigg / \frac{11!}{7!} \\ &= \frac{4! \cdot 7! \cdot 11}{11!} \\ &= \frac{4\cdot 3 \cdot 2}{10 \cdot 9 \cdot 8} \\ &= \frac{1}{30} \end{align*} Alternatively, \begin{align*} \mathbb{P}(\text{all four discs are numbered} | \text{first disc is 3}) &= \frac{\mathbb{P}(\text{all four discs are numbered and first disc is 3})}{\mathbb{P}( \text{first disc is 3})} \\ &= \frac{\binom{4}{3} \Bigg / 11 \cdot \binom{10}{3}}{1/11} \\ &= \frac{1}{30} \end{align*} Where we are calculating this as "choose one number", then "choose 3 more", which can happen ending up with 3, number, number, number in \(\binom{4}{3}\) ways, and there are \(11 \cdot \binom{10}{3}\) was overall. Another alternative using Bayes rule: \begin{align*} \mathbb{P}(\text{all four discs are numbered} | \text{first disc is 3}) &= \mathbb{P}( \text{first disc is 3} | \text{all four discs are numbered}) \frac{ \mathbb{P}( \text{all four discs are numbered} }{ \mathbb{P}( \text{first disc is 3} )} \\ &= \frac{\frac{1}{5} \cdot \frac{1}{66}}{\frac{1}{11}} \\ &= \frac1{30} \end{align*}
  3. \begin{align*} \mathbb{P}(\text{exactly two discs are numbered} | \text{first disc is 3}) &=\frac{\mathbb{P}(\text{exactly two discs are numbered and first disc is 3})}{\mathbb{P}( \text{first disc is 3})} \\ &= \frac{3 \cdot {^4\P_1} \cdot {^{6}\P_2} \big / {^{11}\P_4}}{\frac1{11} } \\ &= \frac12 \end{align*} Alternatively, \begin{align*} \mathbb{P}(\text{exactly two discs are numbered} | \text{first disc is 3}) &=\frac{\mathbb{P}(\text{exactly two discs are numbered and first disc is 3})}{\mathbb{P}( \text{first disc is 3})} \\ &= \frac{\binom{4}{1}\binom{6}{2} \Big / 11 \cdot \binom{10}{3}}{1/11} \\ &= \frac12 \end{align*}
  4. \begin{align*} \mathbb{P}(\text{exactly two discs are numbered} | \text{3 taken}) &= \frac{\mathbb{P}(\text{exactly two discs are numbered and 3 taken})}{\mathbb{P}( \text{3 taken})} \\ &= \frac{\binom{4}{1}\binom{6}{2} \Big / \binom{11}{4}}{\frac{4}{11}} \\ &= \frac{\frac{2}{11}}{\frac4{11}} \\ &= \frac12 \end{align*} Using Bayes rule: \(\mathbb{P}( \text{3 taken}) = \frac{1}{11} + \frac{10}{11}\frac{1}{10} + \frac{10}{11}\frac{9}{10}\frac{1}{9} + \frac{10}{11}\frac{9}{10}\frac89\frac18 = \frac{4}{11}\) \begin{align*} \mathbb{P}(\text{exactly two discs are numbered} | \text{3 taken}) &= \frac{\mathbb{P}(\text{3 taken | exactly two discs are numbered})\mathbb{P}(\text{exactly two discs are numbered})}{\mathbb{P}( \text{3 taken})} \\ &= \frac{\frac{4}{10} \cdot \binom{5}{2} \binom{6}{2} \Big / \binom{11}{4}}{4/11} \\ &= \frac{\frac4{10}{5 / 11}}{4/11} \\ &= \frac{1}{2} \end{align*}
  5. \begin{align*} \mathbb{P}(\text{exactly two discs are numbered} | \text{numbered disc first}) &= \frac{\mathbb{P}(\text{exactly two discs are numbered and numbered disc first})}{\mathbb{P}( \text{numbered disc first})} \\ &= \frac{3 \cdot {^5\P_1}\cdot{^4\P_1}\cdot{^6\P_2} \Big / {^{11}\P_4}}{\frac{5}{11}} \\ &= \frac{1}{2} \end{align*}
  6. \begin{align*} \mathbb{P}(\text{exactly two discs are numbered} | \text{numbered disc taken}) &= \frac{\mathbb{P}(\text{exactly two discs are numbered and numbered disc taken})}{\mathbb{P}(\text{numbered disc taken})} \\ &= \frac{\mathbb{P}(\text{exactly two discs are numbered})}{1 - \mathbb{P}(\text{not numbered discs taken})} \\ &= \frac{\binom{5}{2}\binom{6}{2} \Big / \binom{11}{4}}{1 - \binom{6}{4} \Big / \binom{11}{4}} \\ &= \frac{\frac{5}{11}}{\frac{21}{22}} \\ &= \frac{10}{21} \neq \frac12 \end{align*}

View
2006 Paper 1 Q14
D: 1500.0 B: 1502.6
probability geometric distribution hypergeometric distribution sampling with replacement sampling without replacement optimisation discrete probability

  1. A bag of sweets contains one red sweet and \(n\) blue sweets. I take a sweet from the bag, note its colour, return it to the bag, then shake the bag. I repeat this until the sweet I take is the red one. Find an expression for the probability that I take the red sweet on the \(r\)th attempt. What value of \(n\) maximises this probability?
  2. Instead, I take sweets from the bag, without replacing them in the bag, until I take the red sweet. Find an expression for the probability that I take the red sweet on the \(r\)th attempt. What value of \(n\) maximises this probability?

Solution:

  1. This is the probability of having the sequence \(\underbrace{BB\cdots B}_{r-1 \text{ times}}R\) which has probability \(\displaystyle \left ( \frac{n}{n+1} \right)^{r-1}\frac{1}{n+1}\). Maximising this, is equivalent to maximising \(\log\) of it, ie \begin{align*} && y &= (r-1) \ln n - r \ln (n+1) \\ \Rightarrow && \frac{\d y}{\d n} &= \frac{r-1}{n} - \frac{r}{n+1} \\ &&&= \frac{(r-1)(n+1)-rn}{n(n+1)} \\ &&&= \frac{r-n-1}{n(n+1)} \end{align*} Therefore this is maximised when \(n = r-1\)

View
1999 Paper 1 Q12
D: 1500.0 B: 1516.0
probability inequality AM-GM inequality dice proof by contradiction optimisation discrete probability

  1. Prove that if \(x>0\) then \(x+x^{-1}\ge2.\;\) I have a pair of six-faced dice, each with faces numbered from 1 to 6. The probability of throwing \(i\) with the first die is \(q_{i}\) and the probability of throwing \(j\) with the second die is \(r_{j}\) (\(1\le i,j \le 6\)). The two dice are thrown independently and the sum noted. By considering the probabilities of throwing 2, 12 and 7, show the sums \(2, 3, \dots, 12\) are not equally likely.
  2. The first die described above is thrown twice and the two numbers on the die noted. Is it possible to find values of \(q_{j}\) so that the probability that the numbers are the same is less than \(1/36\)?

Solution:

  1. Notice that if \(x > 0\) we must have \begin{align*} && \left ( \sqrt{x} - \frac{1}{\sqrt{x}} \right)^2 &\geq 0 \\ \Leftrightarrow && x - 2 + x^{-1} & \geq 0 \\ \Leftrightarrow && x + x^{-1} & \geq 2 \end{align*} Let \(S\) be the sum, and assume all probabilities are equal \begin{align*} && \mathbb{P}(S = 2) &= q_1 r_1 \\ && \mathbb{P}(S = 12) &= q_6 r_6 \\ && \mathbb{P}(S = 7) &= \sum_{i=1}^6 q_i r_{7-i} \\ \Rightarrow && q_1r_1 &= q_6r_6 \\ \Rightarrow && q_1r_6+q_6r_1 &\leq q_1r_1 \\ \Rightarrow && \frac{r_6}{r_1} + \frac{q_6}{q_1} &\leq 1 \\ \Rightarrow && q_1r_6+q_6r_1 &\leq q_6r_6 \\ \Rightarrow && \frac{q_1}{q_6} + \frac{r_1}{r_6} &\leq 1 \\ \Rightarrow && \frac{r_6}{r_1} + \frac{q_6}{q_1}+\frac{q_1}{q_6} + \frac{r_1}{r_6} &\leq 2\\ \text{but} && \frac{r_6}{r_1} + \frac{q_6}{q_1}+\frac{q_1}{q_6} + \frac{r_1}{r_6} &\geq 4 \end{align*} Since we have a contradiction they cannot all be equal.
  2. We would like \(\displaystyle \sum q_i^2 \leq 1/36\) (subject to \(\displaystyle \sum q_i = 1\), clearly this cannot be true since: \begin{align*} && 1 &= \left ( \sum_{i=1}^6 q_i \right)^2 \\ &&&= \sum_{i=1}^6 q_i^2 + \sum_{i \neq j} 2q_i q_j \\ &&&\leq \sum_{i=1}^6 q_i^2 + 5\sum_{i=1}^6 q_i^2 \\ &&&=6 \sum_{i=1}^6 q_i^2 \\ \Rightarrow && \sum_{i=1}^6 q_i^2 &\geq 1/6 > 1/36 \end{align*} [For a weaker solution to the last part, notice that the largest value of \(q_i\) is \(\geq 1/6\) and therefore \(q_{max}^2 \geq 1/36\), but if equality holds then the other values must also be non-zero, and therefore the inequality cannot hold]

View