Problems

Filters
Clear Filters

7 problems found

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
2022 Paper 3 Q11
D: 1500.0 B: 1500.0
binomial distribution mean deviation binomial coefficient combinatorial identity expected value symmetry fair coin

A fair coin is tossed \(N\) times and the random variable \(X\) records the number of heads. The mean deviation, \(\delta\), of \(X\) is defined by \[ \delta = \mathrm{E}\big(|X - \mu|\big) \] where \(\mu\) is the mean of \(X\).

  1. Let \(N = 2n\) where \(n\) is a positive integer.
    1. Show that \(\mathrm{P}(X \leqslant n-1) = \frac{1}{2}\big(1 - \mathrm{P}(X=n)\big)\).
    2. Show that \[ \delta = \sum_{r=0}^{n-1}(n-r)\binom{2n}{r}\frac{1}{2^{2n-1}}\,. \]
    3. Show that for \(r > 0\), \[ r\binom{2n}{r} = 2n\binom{2n-1}{r-1}\,. \] Hence show that \[ \delta = \frac{n}{2^{2n}}\binom{2n}{n}\,. \]
  2. Find a similar expression for \(\delta\) in the case \(N = 2n+1\).

Solution:

  1. When \(N = 2n+1\), \(\mu = n +\frac12\) and so \begin{align*} && \delta &= \E[|X-\mu|] \\ &&&= \sum_{i=0}^n (n + \tfrac12 - i) \frac{1}{2^{2n+1}} \binom{2n+1}{i} + \sum_{i=n+1}^{2n+1} (i-n - \tfrac12) \frac{1}{2^{2n+1}} \binom{2n+1}{i} \\ &&&= 2\sum_{i=0}^n (n + \tfrac12 - i) \frac{1}{2^{2n+1}} \binom{2n+1}{i} \\ &&&= \frac{(2n +1)}{2^{2n+1}}\sum_{i=0}^n \binom{2n+1}i - \frac{2}{2^{2n+1}}\sum_{i=0}^n i \binom{2n+1}{i} \\ &&&= \frac{(2n +1)}{2^{2n+1}}\sum_{i=0}^n \binom{2n+1}i - \frac{2}{2^{2n+1}}\sum_{i=1}^n (2n+1) \binom{2n}{i-1} \\ &&&= \frac{(2n +1)}{2^{2n+1}}2^{2n} - \frac{2(2n+1)}{2^{2n+1}}\sum_{i=0}^{n-1} \binom{2n}{i} \\ &&&= \frac{(2n +1)}{2} - \frac{2(2n+1)}{2^{2n+1}} \frac12\left (2^{2n} - \binom{2n}{n} \right) \\ &&&= \frac{2n+1}{2^{2n+1}}\binom{2n}{n} \end{align*}

View
2016 Paper 3 Q1
D: 1700.0 B: 1500.0
integration reduction formula proof by induction trigonometric substitution improper integral completing the square binomial coefficient integration by parts

Let \[ \displaystyle I_n= \int_{-\infty}^\infty \frac 1 {(x^2+2ax+b)^n} \, \d x \] where \(a\) and \(b\) are constants with \(b > a^2\), and \(n\) is a positive integer.

  1. By using the substitution \(x + a = \sqrt{b- a^2} \, \tan u\,\), or otherwise, show that \[ I_1 = \dfrac \pi {\sqrt{b-a^2}}\, . \]
  2. Show that \(2n(b - a^2)\, I_{n+1} =(2n - 1) \, I_n\,\).
  3. Hence prove by induction that \[ I_n =\frac{\pi}{2^{2n-2}( b - a^2)^{n-\frac12}} \, \binom {2n-2}{n-1} \]

Solution:

  1. \(\,\) \begin{align*} && I_1 &= \int_{-\infty}^{\infty} \frac{1}{x^2+2ax+b} \d x \\ &&&= \int_{-\infty}^{\infty} \frac{1}{b-a^2 +(x+a)^2} \d x \\ &&&= \left [ \frac{1}{\sqrt{b-a^2}} \tan^{-1} \frac{x+a}{\sqrt{b-a^2}} \right]_{-\infty}^{\infty} \\ &&&= \frac{\pi}{\sqrt{b-a^2}} \end{align*}
  2. \(\,\) Here is the corrected LaTeX code for the second part, maintaining your exact styling and notation.
  3. \(\,\) \begin{align*} && I_{n} &= \int_{-\infty}^{\infty} \frac{1}{(x^2+2ax+b)^{n}} \d x \\ &&&= \left[ \frac{x}{(x^2+2ax+b)^n} \right]_{-\infty}^{\infty} - \int_{-\infty}^\infty x \cdot \frac{-n(2x+2a)}{(x^2+2ax+b)^{n+1}} \d x \\ &&&= 0 + n \int_{-\infty}^\infty \frac{2x^2+2ax}{(x^2+2ax+b)^{n+1}} \d x \\ &&&= n \int_{-\infty}^\infty \frac{2(x^2+2ax+b) - (2ax+2b)}{(x^2+2ax+b)^{n+1}} \d x \\ &&&= 2n I_n - n \int_{-\infty}^\infty \frac{2ax+2b}{(x^2+2ax+b)^{n+1}} \d x \\ &&&= 2n I_n - n \int_{-\infty}^\infty \frac{a(2x+2a) + 2(b-a^2)}{(x^2+2ax+b)^{n+1}} \d x \\ &&&= 2n I_n - n \int_{-\infty}^\infty \frac{a(2x+2a)}{(x^2+2ax+b)^{n+1}} \d x - 2n(b-a^2) I_{n+1} \\ &&&= 2n I_n - n \left[ \frac{-a}{n(x^2+2ax+b)^n} \right]_{-\infty}^\infty - 2n(b-a^2) I{n+1} \\ &&&= 2n I_n - 0 - 2n(b-a^2) I_{n+1} \\ \Rightarrow && 2n(b-a^2)I_{n+1} &= (2n-1)I_n \end{align*}
  4. \(\,\) \begin{align*} && I_{n+1} &= \frac{2n-1}{2n(b-a^2)} I_n \\ &&&= \frac{2n-1}{2n(b-a^2)} \cdot \frac{2n-3}{2(n-1)(b-a^2)} I_{n-1} \\ &&&= \frac{2n-1}{2n(b-a^2)} \cdot \frac{2n-3}{2(n-1)(b-a^2)} \cdots I_{1} \\ &&&= \frac{(2n-1)(2n-3) \cdots 1}{2n \cdot 2(n-1) \cdots 2 (b-a^2)^n} \frac{\pi}{\sqrt{b-a^2}} \\ &&&= \frac{(2n-1)(2n-3) \cdots 1}{2^n n!} \frac{\pi}{(b-a^2)^{n+\frac12}} \\ &&&= \frac{(2n-1)(2n-3) \cdots 1 \cdot 2n \cdot 2(n-1) \cdots 2}{2^{2n} n!n!} \frac{\pi}{(b-a^2)^{n+\frac12}} \\ &&&= \frac{(2n)!}{2^{2n}n!n!}\frac{\pi}{(b-a^2)^{n+\frac12}} \\ &&&= \frac{\pi}{2^{2n}(b-a^2)^{n+\frac12}} \binom{2n}{n} \\ \Rightarrow && I_n &= \frac{\pi}{2^{2n-2}(b-a^2)^{n-\frac12}} \binom{2n-2}{n-1} \\ \end{align*}

View
2016 Paper 3 Q5
D: 1700.0 B: 1500.0
binomial theorem proof by induction prime numbers inequality divisibility binomial coefficient number theory

  1. By considering the binomial expansion of \((1+x)^{2m+1}\), prove that \[ \binom{ 2m \! +\! 1}{ m} < 2^{2m}\,, \] for any positive integer \(m\).
  2. For any positive integers \(r\) and \(s\) with \(r< s\), \(P_{r,s}\) is defined as follows: \(P_{r,s}\) is the product of all the prime numbers greater than \(r\) and less than or equal to \(s\), if there are any such primes numbers; if there are no such primes numbers, then \(P_{r,s}=1\,\). For example, \(P_{3,7}=35\), \(P_{7,10}=1\) and \(P_{14,18}=17\). Show that, for any positive integer \(m\), \(P_{m+1\,,\, 2m+1} \) divides \(\displaystyle \binom{ 2m \! +\! 1}{ m} \,,\) and deduce that \[ P_{m+1\,,\, 2m+1} < 2^{2m} \,. \]
  3. Show that, if \(P_{1,k} < 4^k\) for \(k = 2\), \(3\), \(\ldots\), \(2m\), then \( P_{1,2m+1} < 4^{2m+1}\,\).
  4. Prove that \(\P_{1,n} < 4^n\) for \(n\ge2\).

Solution:

  1. Notice that \((1+x)^{2m+1} = 1+\binom{2m+1}{1}x+\cdots + \binom{2m+1}{m}x^{m} + \binom{2m+1}{m+1} + \cdots\). Notice also that \(\binom{2m+1}{m} = \binom{2m+1}{m+1}\). Therefore evaluating at \(x = 1\), we see \(2^{2m+1} > \binom{2m+1}{m} + \binom{2m+1}{m+1} = 2 \binom{2m+1}{m} \Rightarrow \binom{2m+1}{m} < 2^{2m}\)
  2. Each prime dividing \(P_{m+1, 2m+1}\) divides the numerator of \(\binom{2m+1}{m}\) since it appears in \((2m+1)!\), but not the denominator, since they wont appear in \(m!\) or \((m+1)!\), and since they are prime they have to appear to divide it. Therefore the must divide \(\binom{2m+1}{m}\) and therefore \(P_{m+1,2m+1}\) must divide that binomail coefficient. Since \(a \mid b \Rightarrow a \leq b\) we must have \(P_{m+1, 2m+1} \leq \binom{2m+1}{m} < 2^{2m}\)
  3. Since \begin{align*} P_{1,2m+1} &= P_{1,m+1}P_{m+1, 2m+1} \tag{split into primes below \(m+1\) and abvoe} \\ &< 4^{m+1}P_{m+1,2m+1} \tag{use the condition from the question}\\ &<4^{m+1}2^{2m} \tag{use our inequality} \\ &= 4^{2m+1} \end{align*}
  4. We proceed by (strong) induction. Base case: (\(n = 2\)): \(P_{1,2} = 2 < 4^2 =16\) Suppose it is true for all \(k=2,3,\cdots,2m\) then it is true for \(k=2m+1\) by the previous part of the question. However it is also true for \(k=2m+2\), since that can never be prime (as n is now an even number bigger than 2). Therefore by the principle of mathematical induction it is true for all \(n\).

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
2003 Paper 1 Q5
D: 1500.0 B: 1500.6
binomial expansion generalised binomial theorem term independent of x binomial coefficient power series fractional powers

  1. In the binomial expansion of \((2x+1/x^{2})^{6}\;\) for \(x\ne0\), show that the term which is independent of \(x\) is \(240\). Find the term which is independent of \(x\) in the binomial expansion of \((ax^3+b/x^{2})^{5n}\,\).
  2. Let \(\f(x) =(x^6+3x^5)^{1/2}\,\). By considering the expansion of \((1+3/x)^{1/2}\,\) show that the term which is independent of \(x\) in the expansion of \(\f(x)\) in powers of \(1/x\,\), for \( \vert x\vert>3\,\), is \(27/16\,\). Show that there is no term independent of \(x\,\) in the expansion of \(\f(x)\) in powers of \(x\,\), for \( \vert x\vert<3\,\).

Solution:

  1. The terms will all be of the form \(x^{6-3k}\), so we are looking for \(\binom{6}{2}2^{4} \cdot 1^2 = 6 \cdot 5 \cdot 8 = 240\) The terms will be \(x^{(5n-k)3 -2k} = x^{15n-5k}\), so we want \(k = 3n\), \(\binom{5n}{3n}a^{5n-3n}b^{5n-2n} = \binom{5n}{3n}a^{2n}b^{3n}\)
  2. Let \(f(x) = (x^6+3x^5)^{1/2}\) If \(|x| > 3\), then consider \begin{align*} && f(x) &= x^3(1+3/x)^{1/2} \\ &&&= x^3 \left (1 + \frac12 \frac{3}{x} +\frac{1}{2!} \frac12\cdot \frac{-1}{2} \left ( \frac{3}{x} \right)^2 + \frac{1}{3!} \frac{1}{2} \cdot \frac{-1}{2} \cdot \frac{-3}{2} \left (\frac{3}{x} \right)^3 + \cdots \right) \\ &&&= \cdots \frac{1}{6} \frac{3}{8} 27x^0 + \cdots \\ &&&= \cdots + \frac{27}{16} + \cdots \end{align*} If \(|x| < 3\) we can consider \(f(0) = 0\) and notice that there must be no term independent of \(x\)

View
1990 Paper 1 Q15
D: 1500.0 B: 1591.4
probability negative binomial distribution conditional probability coin tossing combinatorics binomial coefficient derivation of distribution

A coin has probability \(p\) (\(0 < p < 1\)) of showing a head when tossed. Give a careful argument to show that the \(k\)th head in a series of consecutive tosses is achieved after exactly \(n\) tosses with probability \[ \binom{n-1}{k-1}p^{k}(1-p)^{n-k}\qquad(n\geqslant k). \] Given that it took an even number of tosses to achieve exactly \(k-1\) heads, find the probability that exactly \(k\) heads are achieved after an even number of tosses. If this coin is tossed until exactly 3 heads are obtained, what is the probability that exactly 2 of the heads occur on even-numbered tosses?

Solution: We must have a sequence consisting of \(\underbrace{HTT\cdots TH}_{k-1\text{ heads and }n-k\text{ tails}}\underbrace{H}_{k\text{th head}}\). There are \(\binom{n-1}{k-1}\) ways to chose how to place the \(k-1\) heads in the first \(n-1\) flips, and each sequence has probability \(p^{k-1}(1-p)^{n-k}p\) which gives a probability of \(\displaystyle \binom{n-1}{k-1} p^k (1-p)^{n-k}\). Given that it took an even number of tosses to achieve \(k-1\) heads, this is equivalent to the problem of what is the probability that the first head occurs on an even flip, ie \begin{align*} \mathbb{P}(\text{even flip}) &= \mathbb{P}(2\text{nd flip}) +\mathbb{P}(4\text{th flip}) +\mathbb{P}(6\text{th flip}) + \cdots \\ &= (1-p)p + (1-p)^3p + (1-p)^5p + \cdots \\ &= (1-p)p \left ( \sum_{r=0}^\infty (1-p)^{2r}\right) \\ &= \frac{p(1-p)}{1-(1-p)^2} \\ &= \frac{p(1-p)}{2p-p^2} \\ &= \frac{1-p}{2-p} \end{align*} The ways to achieve \(2\) heads on even tosses are \(EEO\), \(EOE\), \(OEE\). The probability of going from \(O\) to \(E\) is the same as the initial probability of an \(O\) flip, etc. Therefore \begin{align*} \mathbb{P}(EEO) &=\left( \frac{1-p}{2-p} \right)^2 \left ( 1- \frac{1-p}{2-p} \right) \\ &= \left( \frac{1-p}{2-p} \right)^2 \left ( \frac{1}{2-p} \right) \\ \mathbb{P}(EOE) &= \left( \frac{1-p}{2-p} \right) \left ( \frac{1}{2-p} \right)^2 \\ \mathbb{P}(OEE) &= \left ( \frac{1}{2-p} \right)^2 \left( \frac{1-p}{2-p} \right)\\ \mathbb{P}(2 \text{ heads on even tosses}) &= \frac{(1-p)^2 + 2(1-p)}{(2-p)^3} \\ &= \frac{(1-p)(2-p)}{(2-p)^3} \\ &= \frac{1-p}{(2-p)^2} \end{align*}

View