Problems

Filters
Clear Filters

7 problems found

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
2009 Paper 1 Q13
D: 1500.0 B: 1504.1
probability discrete probability distributions expectation combinatorics arrangements counting arguments permutations

I seat \(n\) boys and \(3\) girls in a line at random, so that each order of the \(n+3\) children is as likely to occur as any other. Let \(K\) be the maximum number of consecutive girls in the line so, for example, \(K=1\) if there is at least one boy between each pair of girls.

  1. Find \(\P(K=3)\).
  2. Show that \[\P(K=1)= \frac{n(n-1)}{(n+2)(n+3)}\,. \]
  3. Find \(\E(K)\).

Solution:

  1. If all the girls are say together there are \(n+1\) ways to place the block of 3 girls. There are \(\binom{n+3}{3}\) ways to choose where to place the girls in total, therefore: \begin{align*} && \mathbb{P}(K =3) &= \frac{n+1}{\binom{n+3}3} \\ &&&= \frac{6(n+1)}{(n+3)(n+2)(n+1)} \\ &&&= \frac{6}{(n+3)(n+2)} \end{align*}
  2. If \(K= 1\) then all of the girls are separated. We can place three girls and two boys separating them, then we are allocating \(N-2\) boys to \(4\) gaps, ie \(\binom{N-2+3}{3} = \binom{N+1}{3}\). \begin{align*} && \mathbb{P}(K=3) &= \frac{\binom{n+1}{3}}{\binom{n+3}{3}} \\ &&&= \frac{(n+1)n(n-1)}{(n+3)(n+2)(n+1)} \\ &&&= \frac{n(n-1)}{(n+3)(n+2)} \end{align*}
  3. \(\,\) \begin{align*} \mathbb{E}(K) &= \sum_{k=1}^3 k \mathbb{P}(K=k) \\ &= \frac{6}{(n+3)(n+2)} + 2 \left (1 - \frac{6}{(n+3)(n+2)} - \frac{n(n-1)}{(n+3)(n+2)} \right) + 3\frac{n(n-1)}{(n+3)(n+2)} \\ &= 2+\frac{6-12+n(n-1)}{(n+3)(n+2)} \\ &= 2 + \frac{n^2-n-6}{(n+2)(n+3)}\\ &= 2 + \frac{(n-3)(n+2)}{(n+2)(n+3)} \\ &= 2 + \frac{n-3}{n+3} \\ &= \frac{2n}{n+3} \end{align*}

View
2006 Paper 2 Q13
D: 1600.0 B: 1516.0
probability conditional probability combinatorics permutations optimal stopping secretary problem enumeration summation

I know that ice-creams come in \(n\) different sizes, but I don't know what the sizes are. I am offered one of each in succession, in random order. I am certainly going to choose one - the bigger the better - but I am not allowed more than one. My strategy is to reject the first ice-cream I am offered and choose the first one thereafter that is bigger than the first one I was offered; if the first ice-cream offered is in fact the biggest one, then I have to put up with the last one, however small. Let \(\P_n(k)\) be the probability that I choose the \(k\)th biggest ice-cream, where \(k=1\) is the biggest and \(k=n\) is the smallest.

  1. Show that \(\P_4(1) = \frac{11}{24}\) and find \(\P_4(2)\), \(\P_4(3)\) and \(\P_4(4)\).
  2. Find an expression for \(\P_n(1)\).

View
2001 Paper 1 Q14
D: 1500.0 B: 1516.8
probability combinatorics conditional probability ranking counting arguments permutations verification by enumeration

On the basis of an interview, the \(N\) candidates for admission to a college are ranked in order according to their mathematical potential. The candidates are interviewed in random order (that is, each possible order is equally likely).

  1. Find the probability that the best amongst the first \(n\) candidates interviewed is the best overall.
  2. Find the probability that the best amongst the first \(n\) candidates interviewed is the best or second best overall.
Verify your answers for the case \(N=4\), \(n=2\) by listing the possibilities.

Solution:

  1. The probability the best person falls in the first \(n\) is \(\frac{n}{N}\)
  2. The probability the best two people do not fall in the first \(n\) candidates is \begin{align*} && 1-P &= \frac{\binom{N-2}{n}}{\binom{N}{n}} \\ &&&= \frac{(N-2)(N-3)\cdots(N-2-n+1)}{n!} \frac{n!}{N(N-1)(N-2) \cdots (N-n+1)} \\ &&&= \frac{(N-n)(N-n-1)}{N(N-1)} \\ \Rightarrow && P &= 1- \frac{(N-n)(N-n-1)}{N(N-1)} \\ &&&= \frac{N(N-1) - N(N-1)+n(N-n-1)+Nn}{N(N-1)} \\ &&&= \frac{n(2N-n-1)}{N(N-1)} \end{align*}
If \(N = 4, n = 2\) the possibilities are, the best candidate can be first \(3!\) ways, or second \(3!\) ways, which is \(\frac{12}{24} = \frac{1}{2} = \frac{2}{4} = \frac{n}{N}\) so our formula works. In the case neither of the best two candidates are in the first half, the possibilities are \(3412, 3421, 4312, 4321\), ie \(\frac{4}{24} = \frac16\) chance, so the probability they are selected in the first \(n\) is \(\frac56\). our formula says it should be \(\frac{2 \cdot (2 \cdot 4 - 2 - 1)}{4 \cdot 3} = \frac{2 \cdot 5}{4 \cdot 3} = \frac56\) as desired.

View
1995 Paper 1 Q12
D: 1500.0 B: 1501.9
probability combinatorics arrangements permutations counting arguments gaps method

A school has \(n\) pupils, of whom \(r\) play hocket, where \(n\geqslant r\geqslant2.\) All \(n\) pupils are arranged in a row at random.

  1. What is the probability that there is a hockey player at each end of the row?
  2. What is the probability that all the hockey players are standing together?
  3. By considering the gaps between the non-hockey-players, find the probability that no two hockey players are standing together, distinguishing between cases when the probability is zero and when it is non-zero.

View
1994 Paper 3 Q7
D: 1679.5 B: 1503.1
groups permutations symmetric group S3 cyclic group isomorphism roots of unity element order modular arithmetic subgroup complex numbers

Let \(S_{3}\) be the group of permutations of three objects and \(Z_{6}\) be the group of integers under addition modulo 6. List all the elements of each group, stating the order of each element. State, with reasons, whether \(S_{3}\) is isomorphic with \(Z_{6}.\) Let \(C_{6}\) be the group of 6th roots of unity. That is, \(C_{6}=\{1,\alpha,\alpha^{2},\alpha^{3},\alpha^{4},\alpha^{5}\}\) where \(\alpha=\mathrm{e}^{\mathrm{i}\pi/3}\) and the group operation is complex multiplication. Prove that \(C_{6}\) is isomorphic with \(Z_{6}.\) Is there any (multiplicative or additive) subgroup of the complex numbers which is isomorphic with \(S_{3}\)? Give a reason for your answer.

Solution: \(S_3 \) $\begin{array}{c | c |c |c |c |c |c |} \text{elements} & e & (12) & (13) & (23) & (123) & (132) \\ \text{order} & 1 & 2 & 2 & 2 & 3 & 3 \\ \end{array}$ \(\mathbb{Z}_6\) $\begin{array}{c | c |c |c |c |c |c |} \text{elements} & 0 & 1 & 2 & 3 & 4 & 5 \\ \text{order} & 1 & 6 & 3 & 2 & 3 & 6 \\ \end{array}$ \(S_3\) is not isomorphic to \(\mathbb{Z}_6\) since \(\mathbb{Z}_6\) has two elements of order \(6\) but \(S_3\) has none. Consider the map \(f : \mathbb{Z}_6 \to C_6\) with \(i \mapsto \alpha^i\). This is an isomorphism, since \(i + j \mapsto \alpha^{i+j} = \alpha^i\alpha^j\) \(S_3\) is non-abelian, since \((12)(123) = (23) \neq (13) = (123)(12)\) but multiplication and addition of complex numbers is commutative.

View
1989 Paper 2 Q8
D: 1665.0 B: 1499.2
groups complex numbers transformations permutations roots of unity group order Möbius transformation symmetry group

Let \(\Omega=\exp(\mathrm{i}\pi/3).\) Prove that \(\Omega^{2}-\Omega+1=0.\) Two transformations, \(R\) and \(T\), of the complex plane are defined by \[ R:z\longmapsto\Omega^{2}z\qquad\mbox{ and }\qquad T:z\longmapsto\dfrac{\Omega z+\Omega^{2}}{2\Omega^{2}z+1}. \] Verify that each of \(R\) and \(T\) permute the four point \(z_{0}=0,\) \(z_{1}=1,\) \(z_{2}=\Omega^{2}\) and \(z_{3}=-\Omega.\) Explain, without explicitly producing a group multiplication table, why the smallest group of transformations which contains elements \(R\) and \(T\) has order at least 12. Are there any permutations of these points which cannot be produced by repeated combinations of \(R\) and \(T\)?

Solution: \(R(0) = 0\), \(R(1) = \Omega^2 1 = \Omega^2\), \(R(\Omega^2) = \Omega^4 = -\Omega\), \(R(-\Omega) = -\Omega^3 = 1\) \(T(0) = \frac{\Omega^2}1 = \Omega^2\), \(T(1) = \frac{\Omega + \Omega^2}{2\Omega^2+1} = \frac{2\Omega - 1}{2\Omega-1} = 1\) \(T(\Omega^2) = \frac{\Omega^3 + \Omega^2}{2\Omega^4+1} = \Omega \frac{\Omega^2+\Omega}{-2\Omega+1} = \Omega \frac{2\Omega-1}{-2\Omega+1} = - \Omega\) \(T(-\Omega) = \frac{-\Omega^2 + \Omega^2}{-2\Omega^3+1} = \frac{0}{3} = 0\) Thinking of \(R\) and \(S\) as elements of \(S_4\), we have that \(R = (234), S = (134)\), we can also construct \(RS = (14)(23), R^2S = (12)(34), RSR^2S = (13)(24)\). Therefore we have the subgroups \(\{e, (234), (243)\}\) of order \(3\) and the subgroup \(\{e, (12)(34), (13)(24), (14)(23) \}\) of order \(4\). By Lagrange's theorem this means that both \(3\) and \(4\) divide the order of the group, therefore the group has order divisible by \(12\) (and therefore is at least \(12\)). Yes, we cannot produce any odd permutation, for example \((12)\) cannot be produced. (Since all our generators are even permutations).

View