Problems

Filters
Clear Filters

11 problems found

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
2007 Paper 1 Q1
D: 1500.0 B: 1500.0
combinatorics counting balanced number digit sum summation identity enumeration

A positive integer with \(2n\) digits (the first of which must not be \(0\)) is called a balanced number if the sum of the first \(n\) digits equals the sum of the last \(n\) digits. For example, \(1634\) is a \(4\)-digit balanced number, but \(123401\) is not a balanced number.

  1. Show that seventy \(4\)-digit balanced numbers can be made using the digits \(0, 1, 2, 3\) and \(4\).
  2. Show that \(\frac16 {k \left( k+1 \right) \left( 4k+5 \right) }\) \(4\)-digit balanced numbers can be made using the digits \(0\) to \(k\). You may use the identity $\displaystyle \sum _{r=0}^{n} r^2 \equiv \tfrac{1}{6} {n \left( n+1 \right) \left( 2n+1 \right) } \;$.

Solution:

  1. For each number from \(1\) to \(8\) (4+4), we can count the number of ways it can be achieved in any way, or without including a leading \(0\). \begin{array}{c|c|c|c} \text{total} & \text{ways with }0 & \text{ways without } 0 & \text{comb}\\ \hline 8 & 1 & 1 & 1\\ 7 & 2 & 2 & 4 \\ 6 & 3 & 3 & 9 \\ 5 & 4 & 4 & 16 \\ 4 & 5 & 4 & 20 \\ 3 & 4 & 3 & 12 \\ 2 & 3 & 2 & 6 \\ 1 & 2 & 1 & 2 \\ \hline &&& 70 \end{array}
  2. For \(2k\) to \(k+1\) there are \(1 \times 1 + 2 \times 2 + \cdots i\times i+\cdots + k\times k\) ways to achieve this, (we can choose anything from \(k\) to \(k-i+1\) for the first digit, and we can never have a \(0\). For \(1\) to \(k\) we can have \(1 \times 2 + 2 \times 3 + \cdots + k \times (k+1)\) since we cannot start with a \(0\), but can have anything less than or equal to \(i\) for the first digit, and then with the \(0\) we can have the same thing starting with \(0\). Hence the answer is: \begin{align*} && S &= \sum_{i=1}^k i^2 + \sum_{i=1}^k i (i+1) \\ &&&= 2\sum_{i=1}^k i^2 + \sum_{i=1}^k i \\ &&&= \frac{1}{3} k(k+1)(2k+1) + \frac12k(k+1) \\ &&&= k(k+1) \left (\frac{2k+1}{3} + \frac{1}{2} \right) \\ &&&= \frac16 k(k+1)(4k+2+3) \\ &&&= \frac16 k(k+1)(4k+5) \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
2005 Paper 1 Q1
D: 1500.0 B: 1500.0
combinatorics digit sum stars and bars counting with constraints enumeration integer partitions

\(47231\) is a five-digit number whose digits sum to \(4+7+2+3+1 = 17\,\).

  1. Show that there are \(15\) five-digit numbers whose digits sum to \(43\). You should explain your reasoning clearly.
  2. How many five-digit numbers are there whose digits sum to \(39\)?

Solution:

  1. The largest a five-digit number can have for its digit sum is \(45 = 9+9+9+9+9\). To achieve \(43\) we can either have 4 9s and a 7 or 3 9s and 2 8s. The former can be achieved in \(5\) ways and the latter can be achieved in \(\binom{5}{2} = 10\) ways. (2 places to choose to put the 2 8s). In total this is \(15\) ways.
  2. To achieve \(39\) we can have: \begin{array}{c|l|c} \text{numbers} & \text{logic} & \text{count} \\ \hline 99993 & \binom{5}{1} & 5 \\ 99984 & 5 \cdot 4 & 20 \\ 99974 & 5 \cdot 4 & 20 \\ 99965 & 5 \cdot 4 & 20 \\ 99884 & \binom{5}{2} \binom{3}{2} & 30 \\ 99875 & \binom{5}{2} 3! & 60 \\ 99866 & \binom{5}{2} \binom{3}{2} & 30 \\ 98886 & 5 \cdot 4 & 20 \\ 98877 & \binom{5}{2} \binom{3}{2} & 30 \\ 88887 & \binom{5}{1} & 5 \\ \hline && 240 \end{array}

View
1999 Paper 3 Q4
D: 1700.0 B: 1516.0
proof Euler's formula polyhedron combinatorial argument enumeration regular polyhedra Platonic solids inequality

A polyhedron is a solid bounded by \(F\) plane faces, which meet in \(E\) edges and \(V\) vertices. You may assume \textit{Euler's formula}, that \(V-E+F=2\). In a regular polyhedron the faces are equal regular \(m\)-sided polygons, \(n\) of which meet at each vertex. Show that $$ F={4n\over h} \,, $$ where \(h=4-(n-2)(m-2)\). By considering the possible values of \(h\), or otherwise, prove that there are only five regular polyhedra, and find \(V\), \(E\) and \(F\) for each.

Solution: Note that each of the \(F\) faces have \(m\) edges. If we count edges from each face we will get \(mF\) edges, but this counts each edge twice, so \(E = \frac{m}{2}F\). Similarly each edge goes into \(2\) vertices, but this counts each vertex \(n\) times, therefore \(V = \frac{2E}{n} = \frac{m}{n}F\) Therefore \begin{align*} && 2 &= V - E + F \\ &&&= \frac{m}{n}F - \frac{m}{2}F + F \\ &&&= F \left ( \frac{2m-nm+2n}{2n} \right) \\ &&&= F \left ( \frac{4-(n-2)(m-2)}{2n} \right) \\ \Rightarrow && F &= \frac{4n}{4-(n-2)(m-2)} = \frac{4n}{h} \end{align*} Notice that \(1 \leq h \leq 4\), so If \(h = 4\), then \(n = 2\) or \(m = 2\) but we can't have two-sided polygons or polyhedra with two faces making a vertex so this is not possible. If \(h = 3\) then \((n-2)(m-2) = 1\) and \(3 \mid n\), so we have \(n = 3, m = 3\). ie we have triangular faces meeting at \(3\) per point. We also have \(F = \frac{4 \cdot 3 }3\) which is \(4\) faces so this is a tetrahedron and \((V,E, F) = (4, 6, 4)\) If \(h = 2\) then \((n-2)(m-2) = 2\): Case 1: \(n = 4, m = 3\) which is four triangles meeting at each vertex with \((V,E,F) = (6, 12, 8)\), ie an octohedron. Case 2: \(n = 3, m = 4\) so we have three squares meeting at each vertex, with \((V,E,F) = (8,12,6)\) which is a cube. If \(h = 1\) then \((n-2)(m-2) = 3\) Case 1: \(n = 5, m = 3\) which is five triangles meeting at each vertex, with \((V,E,F) = ( 12,30, 20)\) ie an icosahedron. Case 2: \(n = 3, m = 5\) which is three pentagons meeting at each vertex, with \((V,E,F) = (20, 30,12)\) which is a dodecahedron. These are all the possible cases and hence we have found the five platonic solids.

View
1997 Paper 1 Q1
D: 1484.0 B: 1500.0
combinatorics coin change problem counting enumeration systematic listing integer partitions

Show that you can make up 10 pence in eleven ways using 10p, 5p, 2p and 1p coins. In how many ways can you make up 20 pence using 20p, 10p, 5p, 2p and 1p coins? You are reminded that no credit will be given for unexplained answers.

Solution: Writing out the possibilities in order of the largest coin used (and then second largest and so-on): \begin{align*} && 10 &= 10 \\ &&&= 5 + 5 \\ &&&= 5 + 2 + 2 + 1 \\ &&&= 5 + 2 + 1 + 1 + 1 \\ &&&= 5 + 1 + 1 + 1 + 1 + 1\\ &&&= 2 + 2 + 2 + 2 + 2 = 5 \cdot 2\\ &&&= 4 \cdot 2 + 2 \cdot 1 \\ &&&= 3 \cdot 2 + 4 \cdot 1\\ &&&= 2 \cdot 2 + 6\cdot 1\\ &&&= 1 \cdot 2 + 8\cdot 1 \\ &&&= 10 \cdot 1 \end{align*} For 20p, we have \begin{align*} && 20 &= 20 \\ &&&= 10 + \text{all 11 ways} \\ &&&= 4\cdot 5 \\ &&&= 3\cdot 5 +\text{3 ways} \\ &&&= 2\cdot5 + \text{6 ways} \\ &&&= 1\cdot 5 + \text{8 ways} \\ &&&= k\cdot 2 + (20-2k)\cdot 1 \quad \text{11 ways} \end{align*} ie 41 ways

View
1997 Paper 2 Q1
D: 1600.0 B: 1500.0
sequences digit constraints enumeration summation prime factorization combinatorics arithmetic

Find the sum of those numbers between 1000 and 6000 every one of whose digits is one of the numbers \(0,\,2,\,5\) or \(7\), giving your answer as a product of primes.

Solution: The first digit is \(2\) or \(5\), all the other digits can be any value from \(0,2,5,7\). Therefore we have \begin{align*} S &= 2000 \cdot 4^3+5000 \cdot 4^3 + (200+500+700) \cdot 2 \cdot 4^2 + (20+50+70) \cdot 2 \cdot 4^2 + (2+5+7) \cdot 2 \cdot 4^2 \\ &= 7 \cdot 4^3 \cdot 2^3 \cdot 5^3 + 14 \cdot 2 \cdot 4^2 \cdot 111 \\ &= 2^{9} \cdot5^3 \cdot 7 + 2^{6} \cdot 3 \cdot 7 \cdot 37 \\ &= 2^6 \cdot 7 \cdot (1000+111) \\ &= 2^6 \cdot 7 \cdot 11 \cdot 101 \end{align*} Alternatively, consider adding the first and last terms, and second and second and last terms, etc we obtain \(7777\). There are \(2 \cdot 4^3\) terms so \(7777 \cdot 4^3 = 2^6 \cdot 7 \cdot 11 \cdot 101\)

View
1995 Paper 2 Q3
D: 1600.0 B: 1500.0
proof logic puzzle combinatorics constraint satisfaction integer partitions deduction enumeration

The Tour de Clochemerle is not yet as big as the rival Tour de France. This year there were five riders, Arouet, Barthes, Camus, Diderot and Eluard, who took part in five stages. The winner of each stage got 5 points, the runner up 4 points and so on down to the last rider who got 1 point. The total number of points acquired over the five states was the rider's score. Each rider obtained a different score overall and the riders finished the whole tour in alphabetical order with Arouet gaining a magnificent 24 points. Camus showed consistency by gaining the same position in four of the five stages and Eluard's rather dismal performance was relieved by a third place in the fourth stage and first place in the final stage. Explain why Eluard must have received 11 points in all and find the scores obtained by Barthes, Camus and Diderot. Where did Barthes come in the final stage?

Solution: Since \(A\) scored \(24\) points, he must have finished first in all but one race and second in that race. Given \(E\) won the final stage, \(A\) must have been \(11112\) \begin{array}{c|ccccc|c} & 1 & 2 & 3 & 4& 5 & \sum \\ \hline A & 1 & 1 & 1 & 1 & 2 & 24 \\ B & - & - & - & - & - & \\ C & - & - & - & - & - & \\ D & - & - & - & - & - & \\ E & - & - & - & 3 & 1 \\ \end{array} If \(E\) has \(12\) points the smallest number of points the others can have are \(13, 14, 15\) which would be a total of \(78\) points \(\geq 15 \times 5 = 75\), more than is available, therefore \(E\) must have the minimum \(11\) points. \begin{array}{c|ccccc|c} & 1 & 2 & 3 & 4& 5 & \sum \\ \hline A & 1 & 1 & 1 & 1 & 2 & 24 \\ B & - & - & - & - & - & \\ C & - & - & - & - & - & \\ D & - & - & - & - & - & \\ E & 5 & 5 & 5 & 3 & 1 & 11 \\ \end{array} There are now \(40\) points to be divided between \(B, C\) and \(D\). \(12+13+14 = 39\), so only way to achieve this is \(12, 13, 15\). \begin{array}{c|ccccc|c} & 1 & 2 & 3 & 4& 5 & \sum \\ \hline A & 1 & 1 & 1 & 1 & 2 & 24 \\ B & - & - & - & - & - & 15 \\ C & - & - & - & - & - & 13 \\ D & - & - & - & - & - & 12 \\ E & 5 & 5 & 5 & 3 & 1 & 11 \\ \end{array} Camus gained the same position in four of the five races. So we need \(4x + y = 13\) which can be done with \(4 \times 1 + 9\) or \(4 \times 2 + 5\) or \(4 \times 3 + 1\). The first two aren't possible (you can't score \(9\)) and the second isn't possible (all the first places are taken) so \(C\) must have four third places and a last place. (Which also must be the second to last race since there are alread last places in \(3\) of the races and a third place in the second to last) \begin{array}{c|ccccc|c} & 1 & 2 & 3 & 4& 5 & \sum \\ \hline A & 1 & 1 & 1 & 1 & 2 & 24 \\ B & - & - & - & - & - & 15 \\ C & 3 & 3 & 3 & 5 & 3 & 13 \\ D & - & - & - & - & - & 12 \\ E & 5 & 5 & 5 & 3 & 1 & 11 \\ \end{array} There are now one \(5\), five \(4\)s, four \(2\)s left to place. And they need to add to \(12\) for one rider. [In score terms this is \(1, 5\times 2, 4 \times 4\). Neither rider can have all the second places, and since they would score too highly, and \(D\) can't have more than one second place since otherwise he'd score too highly. Therefore \(B\) has three second places. So \(B\) is \(1,2,4,4,4\) and \(C\) is \(4,2,2,2,2\) in some order. \(D\) can't come second in the last race, so he comes \(4\)th and \(B\) comes \(5\)th \begin{array}{c|ccccc|c} & 1 & 2 & 3 & 4& 5 & \sum \\ \hline A & 1 & 1 & 1 & 1 & 2 & 24 \\ B & - & - & - & - & 5 & 15 \\ C & 3 & 3 & 3 & 5 & 3 & 13 \\ D & - & - & - & - & 4 & 12 \\ E & 5 & 5 & 5 & 3 & 1 & 11 \\ \end{array}

View
1993 Paper 1 Q1
D: 1484.0 B: 1516.0
combinatorics generating functions dice polynomial factorization enumeration integer constraints

I have two dice whose faces are all painted different colours. I number the faces of one of them \(1,2,2,3,3,6\) and the other \(1,3,3,4,5,6.\) I can now throw a total of 3 in two different ways using the two number \(2\)'s on the first die once each. Show that there are seven different ways of throwing a total of 6. I now renumber the dice (again only using integers in the range 1 to 6) with the results shown in the following table \noindent

Total shown by the two dice23456789101112
Different ways of obtaining the total02114386560
\par
Find how I have numbered the dice explaining your reasoning. {[}You will only get high marks if the examiner can follow your argument.{]}

View
1992 Paper 1 Q2
D: 1500.0 B: 1500.0
combinatorics magic square proof enumeration constraint satisfaction systematic counting

A \(3\times3\) magic square is a \(3\times3\) array \[ \begin{array}{ccc} a & b & c\\ d & e & f\\ g & h & k \end{array} \] whose entries are the nine distinct integers \(1,2,3,4,5,6,7,8,9\) and which has the property that all its rows, columns and main diagonals add up to the same number \(n\). (Thus \(a+b+c=d+e+f=g+h+k=a+d+g=b+e+h=c+f+k=a+e+k=c+e+g=n.)\)

  1. Show that \(n=15.\)
  2. Show that \(e=5.\)
  3. Show that one of \(b,d,h\) or \(f\) must have value \(9\).
  4. Find all \(3\times3\) magic squares with \(b=9.\)
  5. How many different \(3\times3\) magic squares are there? Why?
{[}Two magic squares are different if they have different entries in any place of the array.{]}

Solution:

  1. \((a+b+c)+(d+e+f)+(g+h+k) = 3n = 1 + 2 + \cdots + 9 = 45 \Rightarrow n = 15\).
  2. Summing all rows, columns, diagonals through \(e\) we have \((a+e+k)+(b+e+h)+(c+e+g)+(d+e+f) = 45 + 3e = 60 \Rightarrow e = 5\).
  3. Suppose that one of the corners is \(9\), then we need to find \(2\) ways to make \(6\) not using \(5\) and \(1\) (as \(5\) is in the middle and \(1\) diagonally opposite). Clearly this is not possible as the only remaining numbers are \(2,3,4\) and only \(2+4 = 6\). Therefore \(9\) cannot be in the corner or central squares, ie it's one of \(b,d,h,f\)
  4. We must have \begin{array}{ccc} a & 9 & c\\ d & 5 & f\\ g & 1 & k \end{array} and so \(a\) or \(c = 4\). Once we place \(4\) by symmetry there will be another solution with \(a = 2\). So: \begin{array}{ccc} 4 & 9 & 2\\ d & 5 & f\\ g & 1 & k \end{array} we now see \(k\), then \(f\), then \(d\) then \(g\) must be determined, ie: \begin{array}{ccc} 4 & 9 & 2\\ 3 & 5 & 7\\ 8 & 1 & 6 \end{array} so our two solutions must be this and \begin{array}{ccc} 2 & 9 & 4\\ 7 & 5 & 3\\ 6 & 1 & 8 \end{array}
  5. For each of the \(4\) possible placements of \(9\) there are two magic squares, so there are \(8\) possible magic squares, all related by reflection and rotation.

View
1991 Paper 1 Q14
D: 1516.0 B: 1457.1
probability combinatorics triangle inequality counting summation arithmetic series enumeration

A set of \(2N+1\) rods consists of one of each length \(1,2,\ldots,2N,2N+1\), where \(N\) is an integer greater than 1. Three different rods are selected from the set. Suppose their lengths are \(a,b\) and \(c\), where \(a > b > c\). Given that \(a\) is even and fixed, show, by considering the possible values of \(b\), that the number of selections in which a triangle can then be formed from the three rods is \[ 1+3+5+\cdots+(a-3), \] where we allow only non-degenerate triangles (i.e. triangles with non-zero area). Similarly obtain the number of selections in which a triangle may be formed when \(a\) takes some fixed odd value. Write down a formula for the number of ways of forming a non-degenerate triangle and verify it for \(N=3\). Hence show that, if three rods are drawn at random without replacement, then the probability that they can form a non-degenerate triangle is \[ \frac{(N-1)(4N+1)}{2(4N^{2}-1)}. \]

Solution: Suppose we have \(a = 2k\), it is necessary (by the triangle inequality) that \(b + c > a\). So the smallest \(b\) can be is \(k+1\), and then \(c\) must be \(k\) (1 choice). Then \(b\) could be \(k+2\) and \(c\) can be \(k+1\), \(k\), \(k-1\) (3 choices). Suppose \(b = k+i\) then \(c\) can be \(k+i-1, \ldots, k-i+1\) which is \(2i-1\) choices. This works until \(b = 2k-1\) and there are \(2(k-1)-1 = 2k-3 = a-3\) choices. Therefore there are \(1 + 3 + 5 + \cdots + (a-3)\) total choices. If \(a = 2k+1\) then, \(b = k+1\) is not possible \(b = k+2\) we have \(a = k+1, k\) (2 choices) \(b = k+3\) we have \(a = k+2, k+1, k, k-1\) (4 choices) \(b = k + i\) we have \(a = k+i-1, \cdots, k-i+2\) (\(2i-2\) choices) This works until \(b = k+k\) with \(2k-2 = a-3\) choices. So \(2 + 4 + \cdots + (a-3)\) If \(a\) is even, we have \(\left ( \frac{a-2}{2} \right)^2\) If \(a\) is odd we have \(\frac{(a-3)(a-1)}{4}\) Therefore the total number is: \begin{align*} C &= \sum_{k=2}^N \left ( \frac{(2k-2)^2}{4} + \frac{(2k+1-3)(2k+1-1)}{4} \right) \\ &= \sum_{k=2}^N \left ( (k-1)^2 + (k-1)k\right) \\ &= \sum_{k=2}^N (2k^2-3k+1) \\ &= \sum_{k=1}^N (2k^2-3k+1) \\ &= \frac{N(N+1)(2N+1)}{3} - \frac{3N(N+1)}{2} + N \\ &= \frac{N((N+1)(4N+2-9)+6)}{6} \\ &= \frac{N(4N+1)(N-1)}{6} \\ \end{align*} When \(N = 3\) we have \(1, 2, \cdots, 7\) sticks, and so \(a = 4\), \(1\) option \(a = 5\), \(2\) options \(a = 6\) \(4\) options \(a = 7\) \(6\) options for a total of \(13\). \(\frac{3 \cdot 13 \cdot 2}{6} = 13\) so this is promising, There are \(\binom{2N+1}{3}\) ways to choose three sticks (in order) and of those our formula tells us how many are valid, therefore \begin{align*} && P &= \frac{ \frac{N(4N+1)(N-1)}{6} }{\frac{(2N+1)2N(2N-1)}{6}} \\ &&&= \frac{(4N+1)(N-1)}{2(4N^2-1)} \end{align*}

View