Problems

Filters
Clear Filters

68 problems found

2025 Paper 2 Q11
D: 1500.0 B: 1500.0
geometric distribution geometric series differentiation of series expected value binomial theorem combinatorics probability dice strictly increasing sequence approximation

  1. By considering the sum of a geometric series, or otherwise, show that \[\sum_{r=1}^{\infty} rx^{r-1} = \frac{1}{(1-x)^2} \quad \text{for } |x| < 1.\]
  2. Ali plays a game with a fair \(2k\)-sided die. He rolls the die until the first \(2k\) appears. Ali wins if all the numbers he rolls are even.
    1. Find the probability that Ali wins the game. If Ali wins the game, he earns £1 for each roll, including the final one. If he loses, he earns nothing.
    2. Find Ali's expected earnings from playing the game.
  3. Find a simplified expression for \[1 + 2\binom{n}{1}x + 3\binom{n}{2}x^2 + \ldots + (n+1)x^n,\] where \(n\) is a positive integer.
  4. Zen plays a different game with a fair \(2k\)-sided die. She rolls the die until the first \(2k\) appears, and wins if the numbers rolled are strictly increasing in size. For example, if \(k = 3\), she wins if she rolls 2, 6 or 1, 4, 5, 6, but not if she rolls 1, 4, 2, 6 or 1, 3, 3, 6. If Zen wins the game, she earns £1 for each roll, including the final one. If she loses, she earns nothing. Find Zen's expected earnings from playing the game.
  5. Using the approximation \[\left(1 + \frac{1}{n}\right)^n \approx e \quad \text{for large } n,\] show that, when \(k\) is large, Zen's expected earnings are a little over 35\% more than Ali's expected earnings.

Solution:

  1. Note that, \begin{align*} && \sum_{r = 0}^\infty x^r &= \frac{1}{1-x} && |x| < 1\\ \underbrace{\Rightarrow}_{\frac{\d}{\d x}} && \sum_{r = 0}^\infty rx^{r-1} &= \frac{1}{(1-x)^2} && |x| < 1\\ && \sum_{r = 1}^\infty rx^{r-1} &= \frac{1}{(1-x)^2} && |x| < 1\\ \end{align*}
    1. \begin{align*} && \mathbb{P}(\text{Ali wins in }s\text{ rounds}) &= \left ( \frac{k-1}{2k} \right)^{s-1} \frac{1}{2k} \\ \Rightarrow && \mathbb{P}(\text{Ali wins}) &= \sum_{s=1}^\infty \mathbb{P}(\text{Ali wins in }s\text{ rounds}) \\ &&&=\sum_{s=1}^\infty \left ( \frac{k-1}{2k} \right)^{s-1} \frac{1}{2k} \\ &&&= \frac{1}{2k} \sum_{s=0}^\infty \left ( \frac{k-1}{2k} \right)^{s} \\ &&&= \frac{1}{2k} \frac{1}{1 - \frac{k-1}{2k}} \\ &&&= \frac{1}{2k - (k-1)} \\ &&&= \frac{1}{k+1} \end{align*}
    2. \begin{align*} \mathbb{E}(\text{Ali score}) &= \sum_{s=1}^{\infty} s \mathbb{P}(\text{Ali wins in }s\text{ rounds}) \\ &= \sum_{s=1}^{\infty} s \left ( \frac{k-1}{2k} \right)^{s-1} \frac{1}{2k} \\ &= \frac{1}{2k} \frac{1}{\left (1 - \frac{k-1}{2k} \right)^2} \\ &= \frac{2k}{(k+1)^2} \end{align*}
  3. \begin{align*} && (1+x)^{n} &= \sum_{k=0}^n \binom{n}{k} x^k \\ \Rightarrow && x(1+x)^n &= \sum_{k=0}^n \binom{n}{k} x^{k+1} \\ \Rightarrow && (1+x)^n + nx(1+x)^{n-1} &= \sum_{k=0}^n (k+1)\binom{n}{k} x^k \\ \Rightarrow && (1+x)^{n-1}(1+(n+1)x) &= 1 + 2\binom{n}{1}x + 3\binom{n}{2}x^2 + \ldots + (n+1)x^n \end{align*}
  4. \begin{align*} \mathbb{E}(\text{Zen score}) &= \sum_{s=1}^{2k} s \mathbb{P} \left ( \text{Zen gets }s\text{ numbers in increasing order ending with }2k \right) \\ &= \sum_{s=1}^{2k} s \binom{2k-1}{s-1} \frac{1}{(2k)^s} \\ &= \frac{1}{2k}\sum_{s=0}^{2k-1} (s+1) \binom{2k-1}{s} \frac{1}{(2k)^s} \\ &= \frac{1}{2k} \left ( 1 + \frac{1}{2k} \right)^{2k-2} \left ( 1 + (2k-1+1) \frac{1}{2k} \right) \\ &= \frac{1}{k}\left ( 1 + \frac{1}{2k} \right)^{2k-2} \end{align*}
  5. Therefore as \(k \to \infty\) \begin{align*} \frac{\mathbb{E}(\text{Zen score})}{\mathbb{E}(\text{Ali score}) } &= \frac{1}{k}\left ( 1 + \frac{1}{2k} \right)^{2k-2} \big / \frac{2k}{(k+1)^2} \\ &= \frac{(k+1)^2}{2k^2} \cdot \left ( 1 + \frac{1}{2k} \right)^{2k} \cdot \left ( 1 + \frac{1}{2k} \right)^{-2} \\ &\to \frac12 e \approx 2.7/2 = 1.35 \end{align*} ie Zen's expected earnings are \(\approx 35\%\) more.

View
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
2024 Paper 3 Q11
D: 1500.0 B: 1500.0
binomial distribution binomial theorem expectation combinatorics optimisation symmetry argument binomial coefficient identity

In this question, you may use without proof the results \[\sum_{r=0}^{n} \binom{n}{r} = 2^n \quad \text{and} \quad \sum_{r=0}^{n} r\binom{n}{r} = n\,2^{n-1}.\]

  1. Show that \[r\binom{2n}{r} = (2n+1-r)\binom{2n}{2n+1-r}\] for \(1 \leqslant r \leqslant 2n\). Hence show that \[\sum_{r=0}^{2n} r\binom{2n}{r} = 2\sum_{r=n+1}^{2n} r\binom{2n}{r}.\]
  2. A fair coin is tossed \(2n\) times. The value of the random variable \(X\) is whichever is the larger of the number of heads and the number of tails shown. If \(n\) heads and \(n\) tails are shown, then \(X = n\). Show that \[\mathrm{E}(X) = n\left(1 + \frac{1}{2^{2n}}\binom{2n}{n}\right).\]
  3. Show that \(\dfrac{1}{2^{2n}}\dbinom{2n}{n}\) decreases as \(n\) increases.
  4. In a game, you choose a value of \(n\) and pay \(\pounds n\); then a fair coin is tossed \(2n\) times. You win an amount in pounds equal to the larger of the number of heads and the number of tails shown. If \(n\) heads and \(n\) tails are shown, then you win \(\pounds n\). How should you choose \(n\) to maximise your expected winnings per pound paid?

View
2023 Paper 3 Q4
D: 1500.0 B: 1500.0
binomial theorem trigonometric identities polynomial expansion chebyshev polynomials coefficient extraction combinatorics

Let \(n\) be a positive integer. The polynomial \(\mathrm{p}\) is defined by the identity \[\mathrm{p}(\cos\theta) \equiv \cos\big((2n+1)\theta\big) + 1\,.\]

  1. Show that \[\cos\big((2n+1)\theta\big) = \sum_{r=0}^{n} \binom{2n+1}{2r} \cos^{2n+1-2r}\theta\,(\cos^2\theta - 1)^r\,.\]
  2. By considering the expansion of \((1+t)^{2n+1}\) for suitable values of \(t\), show that the coefficient of \(x^{2n+1}\) in the polynomial \(\mathrm{p}(x)\) is \(2^{2n}\).
  3. Show that the coefficient of \(x^{2n-1}\) in the polynomial \(\mathrm{p}(x)\) is \(-(2n+1)2^{2n-2}\).
  4. It is given that there exists a polynomial \(\mathrm{q}\) such that \[\mathrm{p}(x) = (x+1)\,[\mathrm{q}(x)]^2\] and the coefficient of \(x^n\) in \(\mathrm{q}(x)\) is greater than \(0\). Write down the coefficient of \(x^n\) in the polynomial \(\mathrm{q}(x)\) and, for \(n \geqslant 2\), show that the coefficient of \(x^{n-2}\) in the polynomial \(\mathrm{q}(x)\) is \[2^{n-2}(1-n)\,.\]

View
2023 Paper 3 Q12
D: 1500.0 B: 1500.0
combinatorics discrete probability distributions expected value binomial coefficient counting arguments random variables

A drawer contains \(n\) pairs of socks. The two socks in each pair are indistinguishable, but each pair of socks is a different colour from all the others. A set of \(2k\) socks, where \(k\) is an integer with \(2k \leqslant n\), is selected at random from this drawer: that is, every possible set of \(2k\) socks is equally likely to be selected.

  1. Find the probability that, among the socks selected, there is no pair of socks.
  2. Let \(X_{n,k}\) be the random variable whose value is the number of pairs of socks found amongst those selected. Show that \[\mathrm{P}(X_{n,k} = r) = \frac{\dbinom{n}{r}\dbinom{n-r}{2(k-r)}\, 2^{2(k-r)}}{\dbinom{2n}{2k}}\] for \(0 \leqslant r \leqslant k\).
  3. Show that \[r\,\mathrm{P}(X_{n,k} = r) = \frac{k(2k-1)}{2n-1}\,\mathrm{P}(X_{n-1,k-1} = r-1)\,,\] for \(1 \leqslant r \leqslant k\), and hence find \(\mathrm{E}(X_{n,k})\).

View
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
2021 Paper 3 Q12
D: 1500.0 B: 1500.0
indicator random variables independence variance expected value covariance discrete random variables combinatorics

  1. In a game, each member of a team of \(n\) players rolls a fair six-sided die. The total score of the team is the number of pairs of players rolling the same number. For example, if \(7\) players roll \(3, 3, 3, 3, 6, 6, 2\) the total score is \(7\), as six different pairs of players both score \(3\) and one pair of players both score \(6\). Let \(X_{ij}\), for \(1 \leqslant i < j \leqslant n\), be the random variable that takes the value \(1\) if players \(i\) and \(j\) roll the same number and the value \(0\) otherwise. Show that \(X_{12}\) is independent of \(X_{23}\). Hence find the mean and variance of the team's total score.
  2. Show that, if \(Y_i\), for \(1 \leqslant i \leqslant m\), are random variables with mean zero, then \[ \mathrm{Var}(Y_1 + Y_2 + \cdots + Y_m) = \sum_{i=1}^{m} \mathrm{E}(Y_i^2) + 2\sum_{i=1}^{m-1}\sum_{j=i+1}^{m} \mathrm{E}(Y_i Y_j). \]
  3. In a different game, each member of a team of \(n\) players rolls a fair six-sided die. The total score of the team is the number of pairs of players rolling the same even number minus the number of pairs of players rolling the same odd number. For example, if \(7\) players roll \(3, 3, 3, 3, 6, 6, 2\) the total score is \(-5\). Let \(Z_{ij}\), for \(1 \leqslant i < j \leqslant n\), be the random variable that takes the value \(1\) if players \(i\) and \(j\) roll the same even number, the value \(-1\) if players \(i\) and \(j\) roll the same odd number and the value \(0\) otherwise. Show that \(Z_{12}\) is not independent of \(Z_{23}\). Find the mean of the team's total score and show that the variance of the team's total score is \(\dfrac{1}{36}n(n^2 - 1)\).

Solution:

  1. First note that \(\mathbb{P}(X_{ij} = 1) = \frac16\) since it doesn't matter what \(i\) rolls, it only matters that \(j\) rolls the same thing, which happens \(1/6\) of the time. \begin{align*} && \mathbb{P}(X_{12} = 1, X_{23} = 1) &= \mathbb{P}(1, 2\text{ and }3\text{ all roll the same})\\ &&&= \frac{6}{6^3}= \frac1{6^2} \\ &&&= \mathbb{P}(X_{12} = 1)\mathbb{P}(X_{23} = 1) \\ && \mathbb{P}(X_{12} = 1, X_{23} = 0) &= \mathbb{P}(1, 2\text{ roll the same and }3\text{ rolls different}) \\ &&&= \frac{6 \cdot 1 \cdot 5}{6^3} = \frac{5}{6^2} \\ &&&= \mathbb{P}(X_{12} = 1)\mathbb{P}(X_{23} = 0) \\ && \mathbb{P}(X_{12} = 0, X_{23} = 0) &= \mathbb{P}(2, 3 \text{ roll different to} 2)\\ &&&= \frac{6 \cdot 5 \cdot 5}{6^3}= \frac{5^2}{6^2} \\ &&&= \mathbb{P}(X_{12} = 0)\mathbb{P}(X_{23} = 0) \end{align*} Therefore they are independent (the final case is clear by symmetry from case 2). Note that the score is \(S = \sum_{i \neq j} X_{ij}\) so \begin{align*} && \E[S] &= \E \left [ \sum_{i \neq j} X_{ij} \right] \\ &&&= \sum_{i \neq j} \E \left [ X_{ij} \right] \\ &&&= \sum_{i \neq j} \frac16 \\ &&&= \binom{n}{2} \frac16 = \frac{n(n-1)}{12} \\ \\ && \var[S] &= \var \left [ \sum_{i \neq j} X_{ij} \right] \\ &&& \sum_{i \neq j} \var \left [X_{ij} \right] \tag{pairwise ind.} \\ &&&= \binom{n}{2} \frac{5}{36} = \frac{5n(n-1)}{72} \end{align*}
  2. Note that \(\mathbb{P}(Z_{ij} = 1)=\mathbb{P}(Z_{ij} = -1) = \frac{3}{6^2} = \frac{1}{12}\) but that \(\mathbb{P}(Z_{12} = 1, Z_{23} = -1) = 0\). Notice that \(Z_{12}Z_{23}\) is either \(1\) or \(0\) (since \(2\) can't be both odd and even). \(\mathbb{P}(Z_{12}Z_{23} = 1) = \frac{1}{36}\). Notice that \(Z_{ij}, Z_{kl}\) are independent if \(i \neq j \neq k \neq l\) and so \begin{align*} && \E[T] &= \E \left [ \sum_{i \neq j} Z_{ij} \right] \\ &&&= \sum_{i \neq j}\E \left [ Z_{ij} \right] \\ &&&= 0 \\ \\ && \E[T^2] &= \E \left [ \left ( \sum_{i \neq j} Z_{ij} \right)^2 \right] \\ &&&= \E \left [ \sum_{i \neq j} Z_{ij}^2 + \sum_{i \neq j \neq k} Z_{ij}Z_{jk} + \sum_{i \neq j \neq k \neq l} Z_{ij}Z_{kl}\right] \\ &&&= \binom{n}{2} \frac{1}{6} + 2\frac{n(n-1)(n-2)}{2} \frac{1}{36} + 0 \\ &&&= \frac{n(n-1)}{12} + \frac{n(n-1)(n-2)}{6} \\ &&&= \frac{n(n-1)[3 + (n-2)]}{36} \\ &&&= \frac{n(n^2-1)}{36} \end{align*}

View
2019 Paper 2 Q11
D: 1500.0 B: 1500.0
probability combinatorics triangle inequality counting summation uniform distribution discrete random variables

  1. The three integers \(n_1\), \(n_2\) and \(n_3\) satisfy \(0 < n_1 < n_2 < n_3\) and \(n_1 + n_2 > n_3\). Find the number of ways of choosing the pair of numbers \(n_1\) and \(n_2\) in the cases \(n_3 = 9\) and \(n_3 = 10\). Given that \(n_3 = 2n + 1\), where \(n\) is a positive integer, write down an expression (which you need not prove is correct) for the number of ways of choosing the pair of numbers \(n_1\) and \(n_2\). Simplify your expression. Write down and simplify the corresponding expression when \(n_3 = 2n\), where \(n\) is a positive integer.
  2. You have \(N\) rods, of lengths \(1, 2, 3, \ldots, N\) (one rod of each length). You take the rod of length \(N\), and choose two more rods at random from the remainder, each choice of two being equally likely. Show that, in the case \(N = 2n + 1\) where \(n\) is a positive integer, the probability that these three rods can form a triangle (of non-zero area) is $$\frac{n - 1}{2n - 1}.$$ Find the corresponding probability in the case \(N = 2n\), where \(n\) is a positive integer.
  3. You have \(2M + 1\) rods, of lengths \(1, 2, 3, \ldots, 2M + 1\) (one rod of each length), where \(M\) is a positive integer. You choose three at random, each choice of three being equally likely. Show that the probability that the rods can form a triangle (of non-zero area) is $$\frac{(4M + 1)(M - 1)}{2(2M + 1)(2M - 1)}.$$ Note: \(\sum_{k=1}^{K} k^2 = \frac{1}{6}K(K + 1)(2K + 1)\).

Solution:

  1. If \(n_3 = 9\) and we are looking for \(0 < n_1 < n_2 < n_3\) we can consider values for each \(n_2\). \begin{array}{clc|c} n_2 & \text{range} & \text{count} \\ \hline 6 & 4-5 & 2 \\ 7 & 3-6 & 4 \\ 8 & 2-7 & 6 \\ \hline & & 12 \end{array} When \(n_3 = 10\) \begin{array}{clc|c} n_2 & \text{range} & \text{count} \\ \hline 6 & 5 & 1 \\ 7 & 4-6 & 3 \\ 8 & 3-7 & 5 \\ 9 & 2-8 & 7 \\ \hline & & 16 \end{array} When \(n_3 = 2n+1\) we can have \(2 + 4 + \cdots + 2n-2 = n(n-1)\) When \(n_3 = 2n\) we can have \(1 + 3 + \cdots + 2n-3 = (n-1)^2\)
  2. For the 3 rods to form a triangle, it suffices for the sum of the lengths of the shorter rods to be larger than \(N\). When \(N = 2n+1\) there are \(n(n-1)\) ways this can happen, out of \(\binom{2n}{2}\) ways to choos the numbers, ie \begin{align*} && P &= \frac{n(n-1)}{\frac{2n(2n-1)}{2}} \\ &&&= \frac{n-1}{2n-1} \end{align*} When \(N = 2n\) there are \((n-1)^2\) ways this can happen, out of \(\binom{2n-1}{2}\) ways, ie \begin{align*} && P &= \frac{(n-1)^2}{\frac{(2n-1)(2n-2)}{2}} \\ &&&= \frac{n-1}{2n-1} \end{align*}
  3. The number of ways this can happen is: \begin{align*} C &= \sum_{k=3}^{2M+1} \# \{ \text{triangles where }k\text{ is largest} \} \\ &= \sum_{k=1}^{M} \# \{ \text{triangles where }2k+1\text{ is largest} \} +\sum_{k=1}^{M} \# \{ \text{triangles where }2k\text{ is largest} \}\\ &= \sum_{k=1}^{M} n(n-1)+\sum_{k=1}^{M} (n-1)^2\\ &= \sum_{k=1}^{M} (2n^2-3n+1)\\ &= \frac26M(M+1)(2M+1) - \frac32M(M+1) + M \\ &= \frac16 M(4M+1)(M-1) \end{align*} Therefore the probability is \begin{align*} && P &= \frac{M(4M+1)(M-1)}{6 \binom{2M+1}{3}} \\ &&&= \frac{M(4M+1)(M-1)}{(2M+1)2M(2M-1)} \\ &&&= \frac{(4M+1)(M-1)}{2(2M+1)(2M-1)} \end{align*}

View
2019 Paper 3 Q12
D: 1500.0 B: 1485.6
probability independent events combinatorics subsets counting power set intersection of sets inclusion

The set \(S\) is the set of all integers from 1 to \(n\). The set \(T\) is the set of all distinct subsets of \(S\), including the empty set \(\emptyset\) and \(S\) itself. Show that \(T\) contains exactly \(2^n\) sets. The sets \(A_1, A_2, \ldots, A_m\), which are not necessarily distinct, are chosen randomly and independently from \(T\), and for each \(k\) \((1 \leq k \leq m)\), the set \(A_k\) is equally likely to be any of the sets in \(T\).

  1. Write down the value of \(P(1 \in A_1)\).
  2. By considering each integer separately, show that \(P(A_1 \cap A_2 = \emptyset) = \left(\frac{3}{4}\right)^n\). Find \(P(A_1 \cap A_2 \cap A_3 = \emptyset)\) and \(P(A_1 \cap A_2 \cap \cdots \cap A_m = \emptyset)\).
  3. Find \(P(A_1 \subseteq A_2)\), \(P(A_1 \subseteq A_2 \subseteq A_3)\) and \(P(A_1 \subseteq A_2 \subseteq \cdots \subseteq A_m)\).

Solution: For every element in \(S\) we can choose whether or not it appears in a subset of \(S\), therefore there are \(2^n\) choices so \(2^n\) distinct subsets.

  1. \(\mathbb{P}(1 \in A_1) = \frac12\) (since \(1\) is in exactly half the subsets)
  2. \(\,\) \begin{align*} && \mathbb{P}(A_1 \cap A_2 = \emptyset) &= \mathbb{P}(i \not \in (A_1 \cap A_2) \forall i) \\ &&&= \prod_{i=1}^n \left ( 1-\mathbb{P}(i \in A_1 \cap A_2) \right) \\ &&&= \prod_{i=1}^n \left ( 1-\mathbb{P}(i \in A_1)\mathbb{P}(i \in \cap A_2) \right) \\ &&&= \prod_{i=1}^n \left ( 1-\frac12 \cdot \frac12\right) \\ &&&= \left (\frac34 \right)^n \end{align*}
  3. \(\,\) \begin{align*} && \mathbb{P}(A_1 \cap A_2 \cap A_3 = \emptyset) &= \mathbb{P}(i \not \in (A_1 \cap A_2 \cap A_3) \forall i) \\ &&&= \prod_{i=1}^n \left ( 1-\mathbb{P}(i \in A_1 \cap A_2 \cap A_3) \right) \\ &&&= \prod_{i=1}^n \left ( 1-\mathbb{P}(i \in A_1)\mathbb{P}(i \in \cap A_2))\mathbb{P}(i \in \cap A_3) \right) \\ &&&= \prod_{i=1}^n \left ( 1-\frac12 \cdot \frac12 \cdot \frac12\right) \\ &&&= \left (\frac78 \right)^n \end{align*} Similarly, \(\displaystyle \mathbb{P}(A_1 \cap A_2 \cap \cdots \cap A_m = \emptyset) = \left ( \frac{2^m-1}{2^m} \right)^n\)
  4. \(\,\) \begin{align*} && \mathbb{P}(A_1 \subseteq A_2) &= \mathbb{P}(A_1 \cap A_2^c = \emptyset) \\ &&&= \left (\frac34 \right)^n \\ \\ && \mathbb{P}(A_1 \subseteq A_2 \subseteq A_3) &= \prod_{i=1}^n \mathbb{P}(\text{once }i\text{ appears it keeps appearing}) \\ &&&= \prod_{i=1}^n \frac{\#\{(0,0,0), (0,0,1), (0,1,1), (1,1,1) \}}{2^3} \\ &&&= \prod_{i=1}^n \frac{4}{8} \\ &&&= \frac{1}{2^n} \\ \\ && \mathbb{P}(A_1 \subseteq A_2 \subseteq \cdots \subseteq A_m) &= \prod_{i=1}^n \frac{m+1}{2^m} \\ &&&= \left ( \frac{m+1}{2^m} \right)^n \end{align*}

View
2018 Paper 1 Q5
D: 1484.0 B: 1516.0
polynomials remainder theorem factor theorem integer coefficients divisibility degree 4 polynomial combinatorics proof by contradiction

  1. Write down the most general polynomial of degree 4 that leaves a remainder of 1 when divided by any of \(x-1\,\), \(x-2\,\), \(x-3\,\) or \(x-4\,\).
  2. The polynomial \(\P(x)\) has degree \(N\), where \(N\ge1\,\), and satisfies \[ \P(1) = \P(2) = \cdots = \P(N) =1\,. \] Show that \(\P(N+1) \ne 1\,\). Given that \(\P(N+1)= 2\,\), find \(\P(N+r)\) where \(r\) is a positive integer. Find a positive integer \(r\), independent of \(N,\) such that \(\P(N+r) = N+r\,\).
  3. The polynomial \({\rm S}(x)\) has degree 4. It has integer coefficients and the coefficient of \(x^4\) is 1. It satisfies \[ {\rm S}(a) = {\rm S}(b) = {\rm S}(c) = {\rm S}(d) = 2001\,, \] where \(a\), \(b\), \(c\) and \(d\) are distinct (not necessarily positive) integers.
    • Show that there is no integer \(e\) such that \({\rm S}(e) = 2018\,\).
    • Find the number of ways the (distinct) integers \(a\), \(b\), \(c\) and \(d\) can be chosen such that \({\rm S}(0) = 2017\) and \(a < b< c< d\,.\)

Solution:

  1. \(p(x) = C(x-1)(x-2)(x-3)(x-4)+1\)
  2. Suppose \(P(N+1) = 1\) them we could consider \(f(x) = P(x) - 1\) to be a polynomial of degree \(N\) with at least \(N+1\) roots, which would be a contradiction. Therefore \(P(N+1) \neq 1\). Since \(P(x) = C(x-1)(x-2)\cdots(x-N) + 1\) and \(P(N+1) = 2\) we must have \(C \cdot N! + 1 = 2 \Rightarrow C = \frac{1}{N!}\), hence \(P(x) = \binom{x-1}{N} + 1\) ie \(P(N+r) = \binom{N+r-1}{N}+1\) so \(P(N+2) = \binom{N+1}{N} +1= N+2\), so we can take \(r=2\).
    1. Suppose consider \(p(x) = S(x) - 2001\), then \(p(x)\) has roots \(a,b,c,d\) and suppose we can find \(e\) such that \(p(e) = 17\) then we must have \((e-a)(e-b)(e-c)(e-d) = 17\) but the only possible factors of \(17\) are \(-17,-1,1,17\) and we cannot have all \(4\) of them. Hence this is not possible.
    2. Now we have \(abcd = 16\), so we can have factors \(-16,-8,-4, -2, -1, 1, 2, 4,8,16\) (and we need to have \(4\) of them). If we have \(0\) negatives, the smallest product is \(1 \cdot 2 \cdot 4 \cdot 8 > 16\) If we have \(2\) negatives we must have \(1\) and \(-1\) (otherwise we have the same problem of being too large. So \(\{-1,1,-2,8\},\{-1,1,2,-8\},\{-1,1,-4,4\},\) If we have \(4\) negatives that's the same issue as with \(0\) negatives.

View
2016 Paper 1 Q12
D: 1516.0 B: 1484.7
probability coin tossing conditional probability combinatorics symmetry argument binomial distribution enumeration

  1. Alice tosses a fair coin twice and Bob tosses a fair coin three times. Calculate the probability that Bob gets more heads than Alice.
  2. Alice tosses a fair coin three times and Bob tosses a fair coin four times. Calculate the probability that Bob gets more heads than Alice.
  3. Let \(p_1\) be the probability that Bob gets the same number of heads as Alice, and let~\(p_2\) be the probability that Bob gets more heads than Alice, when Alice and Bob each toss a fair coin \(n\) times. Alice tosses a fair coin \(n\) times and Bob tosses a fair coin \(n+1\) times. Express the probability that Bob gets more heads than Alice in terms of \(p_1\) and \(p_2\), and hence obtain a generalisation of the results of parts (i) and (ii).

Solution:

  1. There are several possibilities \begin{array}{c|c|c} \text{Alice} & \text{Bob} & P \\ \hline 0 & 1 & \frac1{2^2} \cdot 3 \cdot \frac{1}{2^3} = \frac{3}{2^5} \\ 0 & 2 & \frac1{2^2} \cdot 3 \cdot \frac{1}{2^3} = \frac{3}{2^5} \\ 0 & 3 & \frac1{2^2} \cdot \frac{1}{2^3} = \frac{1}{2^5} \\ 1 & 2 & 2 \cdot \frac1{2^2} \cdot 3 \cdot \frac{1}{2^3} = \frac{6}{2^5} \\ 1 & 3 & 2\cdot \frac1{2^2} \cdot \frac{1}{2^3} = \frac{2}{2^5} \\ 2 & 3 & \frac1{2^2} \cdot \frac{1}{2^3} = \frac{1}{2^5} \\ \hline && \frac{1}{2^5}(3+3+1+6+2+1) = \frac{16}{2^5} = \frac12 \end{array}
  2. There are several possibilities \begin{array}{c|c|c} A & B & \text{count} \\ \hline 0 & 1 & 4 \\ 0 & 2 & 6 \\ 0 & 3 & 4 \\ 0 & 4 & 1 \\ 1 & 2 & 3\cdot6 \\ 1 & 3 & 3\cdot4 \\ 1 & 4 & 3 \\ 2 & 3 & 3\cdot4 \\ 2 & 4 & 3 \\ 3 & 4 & 1 \\ \hline && 64 \end{array} Therefore the total probability is \(\frac12\)
  3. \(\mathbb{P}(\text{Bob more than Alice}) = p_1 \cdot \underbrace{\frac12}_{\text{he wins by breaking the tie on his last flip}} + p_2\) If \(p_3\) is the probability that Alice gets more heads than Bob, then by symmetry \(p_3 = p_2\) and \(p_1 + p_2 + p_3 = 1\). Therefore \(p_1 + 2p_2 = 1\). ie \(\frac12 p_1 + p_2 = \frac12\) therefore the answer is always \(\frac12\) for all values of \(n\).

View
2016 Paper 2 Q12
D: 1600.0 B: 1503.2
probability principle of inclusion-exclusion derangements combinatorics proof fixed points permutations

Starting with the result \(\P(A\cup B) = \P(A)+P(B) - \P(A\cap B)\), prove that \[ \P(A\cup B\cup C) = \P(A)+\P(B)+\P(C) - \P(A\cap B) - \P(B\cap C) - \P(C \cap A) + \P(A\cap B\cap C) \,. \] Write down, without proof, the corresponding result for four events \(A\), \(B\), \(C\) and \(D\). A pack of \(n\) cards, numbered \(1, 2, \ldots, n\), is shuffled and laid out in a row. The result of the shuffle is that each card is equally likely to be in any position in the row. Let \(E_i\) be the event that the card bearing the number \(i\) is in the \(i\)th position in the row. Write down the following probabilities:

  1. \(\P(E_i)\);
  2. \(\P(E_i\cap E_j)\), where \(i\ne j\);
  3. \(\P(E_i\cap E_j\cap E_k)\), where \(i\ne j\), \(j\ne k\) and \(k\ne i\).
Hence show that the probability that at least one card is in the same position as the number it bears is \[ 1 - \frac 1 {2!} + \frac 1{3!} - \cdots + (-1)^{n+1} \frac 1 {n!}\,. \] Find the probability that exactly one card is in the same position as the number it bears

Solution: \begin{align*} && \mathbb{P}(A \cup B \cup C) &= \mathbb{P}(A \cup B) + \mathbb{P}(C) - \mathbb{P}((A \cup B) \cap C) \tag{applying with \(A\cup B\) and \(C\)} \\ &&&= \mathbb{P}(A \cup B) + \mathbb{P}(C) - \mathbb{P}((A \cap C) \cup (B \cap C)) \\ &&&= \mathbb{P}(A)+\mathbb{P}(B) - \mathbb{P}(A\cap B) + \mathbb{P}(C) - \mathbb{P}((A \cap C) \cup (B \cap C)) \tag{applying with \(A\) and \(B\)}\\ &&&= \mathbb{P}(A)+\mathbb{P}(B) - \mathbb{P}(A\cap B) + \mathbb{P}(C) - \left ( \mathbb{P}(A \cap C) +\mathbb{P}(B \cap C) - \mathbb{P}( (A \cap C) \cap (B \cap C) )\right) \\ &&&= \mathbb{P}(A)+\mathbb{P}(B) +\mathbb{P}(C)- \mathbb{P}(A\cap B)- \mathbb{P}(A \cap C) -\mathbb{P}(B \cap C)+\mathbb{P}( A \cap B \cap C) \end{align*} \[ \mathbb{P}(A_1 \cup A_2 \cup A_3 \cup A_4) = \sum_i \mathbb{P}(A_i) - \sum_{i \neq j} \mathbb{P}(A_i \cap A_j) + \sum_{i \neq j \neq j} \mathbb{P}(A_i \cap A_j \cap A_k) - \mathbb{P}(A_1 \cap A_2 \cap A_3 \cap A_4) \]

  1. \(\mathbb{P}(E_i) = \frac{1}{n}\)
  2. \(\mathbb{P}(E_i \cap E_j) = \frac{1}{n} \cdot \frac{1}{n-1} = \frac{1}{n(n-1)}\)
  3. \(\mathbb{P})(E_i \cap E_j \cap E_k) = \frac{1}{n(n-1)(n-2)}\)
First notice that the probability that \(k\) (or more) cards are in the correct place is \(\frac{(n-k)!}{n!}\) (place the other \(n-k\) cards in any order. We are interested in: \begin{align*} \mathbb{P} \left ( \bigcup_{i=1}^n E_i \right) &= \sum_{i} \mathbb{P}(E_i) - \sum_{i \neq j} \mathbb{P}(E_i \cap E_j) + \sum_{i \neq j \neq k} \mathbb{P}(E_i \cap E_j \cap E_k) - \cdots \\ &= \sum_i \frac1n - \sum_{i\neq j} \frac{1}{n(n-1)} + \sum_{i \neq j \neq k} \frac{1}{n(n-1)(n-2)} - \cdots + (-1)^{k+1} \sum_{i_1 \neq i_2 \neq \cdots \neq i_k} \frac{(n-k)!}{n!} + \cdots\\ &= 1 - \binom{n}{2} \frac{1}{n(n-1)} + \binom{n}{3} \frac{1}{n(n-1)(n-2)} - \cdots + (-1)^{k+1} \binom{n}{k} \frac{(n-k)}{n!} + \cdots \\ &= 1 - \frac12 + \frac1{3!} - \cdots + (-1)^{k+1} \frac{n!}{k!(n-k)!} \frac{(n-k)!}{n!} + \cdots \\ &= 1 - \frac1{2!} + \frac1{3!} - \cdots + (-1)^{k+1} \frac{1}{k!} + \cdots + (-1)^{n+1} \frac{1}{n!} \end{align*} The probability exactly one card is in the right place is the probability none of the other \(n-1\) are in the right place, which is: \(\frac1n \left (1 - \left (1 - \frac1{2!} + \frac1{3!} - \cdots + (-1)^{k+1} \frac{1}{k!} + \cdots + (-1)^{n} \frac{1}{(n-1)!} \right) \right)\) but there are also \(n\) cards we can choose to be the card in the right place, hence \(\frac{1}{2!} - \frac{1}{3!} + \cdots +(-1)^n \frac{1}{(n-1)!}\)

View
2015 Paper 2 Q3
D: 1600.0 B: 1483.4
combinatorics proof by induction triangles triangle inequality counting summation closed form formula

Three rods have lengths \(a\), \(b\) and \(c\), where \(a< b< c\). The three rods can be made into a triangle (possibly of zero area) if \(a+b\ge c\). Let \(T_{n}\) be the number of triangles that can be made with three rods chosen from \(n\) rods of lengths \(1\), \(2\), \(3\), \(\ldots\) , \(n\) (where \(n\ge3\)). Show that \(T_8-T_7 = 2+4+6\) and evaluate \(T_8 -T_6\). Write down expressions for \(T_{2m}-T_{2m-1}\) and \(T_{2m} - T_{2m-2}\). Prove by induction that \(T_{2m}=\frac 16 m (m-1)(4m+1)\,\), and find the corresponding result for an odd number of rods.

Solution: Every \(T_7\) triangle is valid, so we are interested in new triangles which have \(8\) has a longest side. We can have: \begin{array}{c|c|c} \text{longest} & \text{middle} & \text{shortest} \\ \hline 8 & 7 & 1-6 \\ 8 & 6 & 2-5 \\ 8 & 5 & 3-4 \end{array} which is \(6+4+2\) extra triangles. The new ones excluding all the sixes are: \begin{array}{c|c|c} \text{longest} & \text{middle} & \text{shortest} \\ \hline 8 & 7 & 1-6 \\ 8 & 6 & 2-5 \\ 8 & 5 & 3-4 \\ 7 & 6 & 1-5 \\ 7 & 5 & 2-4 \\ 7 & 4 & 3 \\ \end{array} Ie \(2+4+6 + 1 + 3+5\) \(T_{2m}-T_{2m-1} = 2 \frac{(m-1)m}{2} = m(m-1)\) and \(T_{2m}-T_{2m-2} = \frac{(2m-2)(2m-1)}{2}\) \(T_4 = 3\) (\(1,2,3\), \(1,3,4\), \(2,3,4\)) and \(\frac16 \cdot 2 \cdot 1 \cdot 9 = 3\) so the base case holds. Suppose it's true for some \(m = k\), then \begin{align*} && T_{2(k+1)} &= T_{2k} + \frac{2m(2m+1)}{2} \\ &&&= \frac{m(m-1)(4m+1)}{6} + \frac{6m(2m+1)}{6}\\ &&&= \frac{m(4m^2-3m-1+12m+6)}{6} \\ &&&= \frac{m(4m^2+9m+5)}{6}\\ &&&= \frac{m(4m+5)(m+1)}{6}\\ &&&= \frac{(m+1-1)(4(m+1)+5)(m+1)}{6}\\ \end{align*} as required, therefore it is true by induction. For odd numbers, we can see that \(T_{2m-1} = \frac{m(m-1)(4m+1)}{6} - m(m-1) = \frac{m(m-1)(4m-5)}{6}\)

View
2013 Paper 1 Q12
D: 1500.0 B: 1468.0
probability combinatorics random selection binomial coefficient Stirling's approximation counting arguments conditional probability

Each day, I have to take \(k\) different types of medicine, one tablet of each. The tablets are identical in appearance. When I go on holiday for \(n\) days, I put \(n\) tablets of each type in a container and on each day of the holiday I select \(k\) tablets at random from the container.

  1. In the case \(k=3\), show that the probability that I will select one tablet of each type on the first day of a three-day holiday is \(\frac9{28}\). Write down the probability that I will be left with one tablet of each type on the last day (irrespective of the tablets I select on the first day).
  2. In the case \(k=3\), find the probability that I will select one tablet of each type on the first day of an \(n\)-day holiday.
  3. In the case \(k=2\), find the probability that I will select one tablet of each type on each day of an \(n\)-day holiday, and use Stirling's approximation \[ n!\approx \sqrt{2n\pi} \left(\frac n\e\right)^n \] to show that this probability is approximately \(2^{-n} \sqrt{n\pi\;}\).

Solution:

  1. The probability the first is different to the second is \(\frac68\), the probability the third is different to both of the first two is \(\frac37\) therefore the probability is \(\frac{6}{8} \cdot \frac37 = \frac9{28}\) Whatever pills we are left with on the last day is essentially the same random choice as we make on the first day, therefore \(\frac9{28}\)
  2. The probability the first is different to the second is \(\frac{2n}{3n-1}\), the probability the third is different to both of the first two is \(\frac{n}{3n-2}\) therefore the probability is \(\frac{2n^2}{(3n-1)(3n-2)}\). [We can also view this as \(\frac{(3n) \cdot (2n) \cdot n}{(3n) \cdot (3n-1) \cdot (3n-2)}\)]
  3. Suppose describe the pills as \(B\) and \(R\) and also number them, then we must have a sequence of the form: \[ B_1R_1 \, B_2R_2 \, B_3R_3 \, \cdots \, B_{n}R_n \] However, we can also rearrange the order of the \(B\) and \(R\) pills in \(n!\) ways each, and also the order of the pairs in \(2^n\) ways. There are \((2n)!\) orders we could have taken the pills out therefore the probability is \begin{align*} && P &= \frac{2^n (n!)^2}{(2n)!} = \frac{2^n}{\binom{2n}{n}} \\ &&&\approx \frac{2^n \cdot 2n \pi \left ( \frac{n}{e} \right)^{2n}}{\sqrt{2 \cdot 2n \cdot \pi} \left ( \frac{2n}{e} \right)^{2n}} \\ &&&= \frac{2^n \sqrt{n \pi} \cdot n^{2n} \cdot e^{-2n}}{2^{2n} \cdot n^{2n} \cdot e^{-2n}} \\ &&&= 2^{-n} \sqrt{n \pi} \end{align*} There is a nice way to think about this question using conditional probability. Suppose we are drawing out of an infinitely supply of \(R\) and \(B\) pills, then each day there is a \(\frac12\) chance of getting different pills. Therefore over \(n\) days there is a \(2^{-n}\) chance of getting different pills. Conditional on the balanced total we see that \begin{align*} && \mathbb{P}(\text{balanced every day} |\text{balanced total}) &= \frac{\mathbb{P}(\text{balanced every day})}{\mathbb{P}(\text{balanced total})} \end{align*} We have already seen the term that is balanced total is \(\frac{1}{2^{2n}}\binom{2n}{n}\), but we can also approximate the balanced total using a normal approximation. \(B(2n, \tfrac12) \approx N(n, \frac{n}{2})\) and so: \begin{align*} \mathbb{P}(X = n) &\approx \mathbb{P}\left (n-0.5 \leq \sqrt{\tfrac{n}{2}} Z + n \leq n+0.5 \right) \\ &= \mathbb{P}\left (- \frac1{\sqrt{2n}} \leq Z \leq \frac{1}{\sqrt{2n}} \right) \\ &= \int_{- \frac1{\sqrt{2n}}}^{\frac1{\sqrt{2n}}} \frac{1}{\sqrt{2\pi}} e^{-x^2/2} \d x \approx \frac{2}{\sqrt{2n}} \frac{1}{\sqrt{2\pi}} \\ &\approx \frac{1}{\sqrt{n\pi}} \end{align*}

View
2013 Paper 1 Q13
D: 1516.0 B: 1532.0
probability discrete probability distribution expectation combinatorics hypergeometric complementary pairs random selection

From the integers \(1, 2, \ldots , 52\), I choose seven (distinct) integers at random, all choices being equally likely. From these seven, I discard any pair that sum to 53. Let \(X\) be the random variable the value of which is the number of discarded pairs. Find the probability distribution of \(X\) and show that \(\E (X) = \frac 7 {17}\). Note: \(7\times 17 \times 47 =5593\).

Solution: There are \(\binom{26}3\binom{23}{1}2\) ways to obtain \(3\) pairs There are \(\binom{26}2 \binom{24}3 \cdot 2^3\) ways to obtain \(2\) pairs There are \(\binom{26}1 \binom{25}5 \cdot 2^5\) ways to obtain \(1\) pairs There are \(\binom{26}7 \cdot 2^7\) ways to obtain \(0\) pairs There are \(\binom{52}{7}\) ways to choose our integers, so \begin{align*} && \mathbb{P}(X = 3) &= \frac{\binom{26}{3} \cdot \binom{23}{1} \cdot 2}{\binom{52}{7}} \\ &&&= \frac{7! \cdot 26 \cdot 25 \cdot 24 \cdot 23 \cdot 2}{3! \cdot 52 \cdot 51 \cdot 50 \cdot 49 \cdot 48 \cdot 47 \cdot 46} \\ &&&= \frac{7 \cdot 6 \cdot 5 \cdot 4 }{51 \cdot 2\cdot 49 \cdot 2\cdot 47 \cdot 2} \\ &&&= \frac{ 5 }{17\cdot 7\cdot 47} = \frac{5}{5593} \\ \\ && \mathbb{P}(X = 2) &= \frac{\binom{26}2 \binom{24}3 \cdot 2^3}{\binom{52}{7}} \\ &&&= \frac{220}{5593} \\ \\ && \mathbb{P}(X = 1) &= \frac{\binom{26}1 \binom{25}5 \cdot 2^5}{\binom{52}{7}} \\ &&&= \frac{1848}{5593} \\ \\ && \mathbb{P}(X = 0) &= \frac{\binom{26}7 \cdot 2^7}{\binom{52}{7}} \\ &&&= \frac{3520}{5593} \\ \\ && \mathbb{E}(X) &= \frac{1848}{5593} + 2 \cdot \frac{220}{5593} + 3 \cdot \frac{5}{5593} \\ &&&= \frac{2303}{5593} = \frac{7}{17} \end{align*} Notice we can find the expected value directly: Let \(X_i\) be the random variable the \(i\)th number is discarded. Notice that \(\mathbb{E}(X) = \mathbb{E}\left (\frac12 \left (X_1 +X_2 +X_3 +X_4 +X_5 +X_6 +X_7\right) \right)\) and also notice that each \(X_i\) has the same distribution (although not independent!). Then \begin{align*} &&\mathbb{E}(X) &= \frac72 \mathbb{E}(X_i) \\ &&&= \frac72 \cdot \left (1 - \frac{50}{51} \cdot \frac{49}{50} \cdots \frac{45}{46} \right) = \frac74 \left ( 1 - \frac{45}{51}\right) \\ &&&= \frac72 \cdot \frac{6}{51} \\ &&&= \frac7{17} \end{align*}

View