Problems

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

Solution:

1. \begin{align*} u = 1+(\alpha-1)x: && \int_0^1 (1 + (\alpha - 1)x)^n \d x &= \int_{u=1}^{u=\alpha} u^n \frac{1}{\alpha - 1} \d u \\ &&&= \left [\frac{u^{n+1}}{(n+1)(\alpha-1)} \right]_1^\alpha \\ &&&= \frac{\alpha^{n+1}-1}{(n+1)(\alpha-1)} \end{align*}
2. \begin{align*} && \int_0^1 (\alpha x + (1-x))^n \d x &= \int_0^1 \sum_{k=0}^n \binom{n}{k} \alpha^k x^k (1-x)^{n-k} \d x \\ &&&= \sum_{k=0}^n \alpha^k \int_0^1 \binom{n}{k} x^k (1-x)^{n-k} \d x \end{align*} Therefore the coefficient of \(\alpha^k\) is \(\displaystyle \int_0^1 \binom{n}{k} x^k (1-x)^{n-k} \d x\)
3. The coefficient of \(\alpha^{k}\) in \(\displaystyle \frac{\alpha^{n+1}-1}{(n+1)(\alpha-1)}\) is \(\displaystyle \frac1{n+1}\). Therefore \begin{align*} && \frac1{n+1} &= \binom{n}{k} \int_0^1 x^k(1-x)^{n-k} \d x \\ \Rightarrow && \int_0^1 x^k (1-x)^{n-k} \d x &= \frac{k!(n-k)!}{(n+1)n!} \\ &&&= \frac{k!(n-k)!}{(n+1)!} \end{align*}

Solution: If the highest mark is \(k\), then there are \(n-1\) remaining marks to give, and they have to be chosen from the numbers \(1, 2, \ldots, k-1\), ie in \(\binom{k-1}{n-1}\) ways. There are \(n\) numbers to be chosen from \(1, 2, \ldots, m\) in total, therefore \(\displaystyle \mathbb{P}(K=k) = \left.\binom{k-1}{n-1} \right/ \binom{m}{n}\) Since \(K\) can take any of the values \(n, \cdots, m\), we must have \begin{align*} && 1 &= \sum_{k=n}^m \mathbb{P}(K=k) \\ &&&= \sum_{k=n}^m \left.\binom{k-1}{n-1} \right/ \binom{m}{n} \\ \Rightarrow && \binom{m}{n} &= \sum_{k=n}^m \binom{k-1}{n-1} \\ \\ && \mathbb{E}(K) &= \sum_{k=n}^m k \cdot \mathbb{P}(K=k) \\ &&&= \sum_{k=n}^m k \cdot \left.\binom{k-1}{n-1} \right/ \binom{m}{n} \\ &&&= n\binom{m}{n}^{-1} \sum_{k=n}^m \frac{k}{n} \cdot \binom{k-1}{n-1} \\ &&&= n\binom{m}{n}^{-1} \sum_{k=n}^m \binom{k}{n} \\ &&&= n\binom{m}{n}^{-1} \sum_{k=n+1}^{m+1} \binom{k-1}{n+1-1} \\ &&&= n\binom{m}{n}^{-1} \binom{m+1}{n+1} \\ &&&= n \cdot \frac{m+1}{n+1} \end{align*}

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}

Solution:

1. \(\frac{2}{28} = \frac{1}{14}\)
2. \(1-\frac{27}{28}\frac{26}{27}\frac{25}{26} = \frac{3}{28}\)
3. \(1 - \frac{26}{28}\frac{25}{27}\frac{24}{26} = \frac{13}{63}\)
4. \(1-\frac{26}{27}\frac{25}{26} = \frac{2}{27}\)
5. \(\frac{1}{27}\)
6. There are \(\binom{2}{1} \binom{26}{2} + \binom{2}{2}\binom{26}{1}\) ways to choose at least one single sex college and \( \binom{2}{2}\binom{26}{1}\) ways to choose both, therefore \begin{align*} P &= \frac{ \binom{2}{2}\binom{26}{1}}{\binom21 \binom{26}2+ \binom{2}{2}\binom{26}{1}} \\ &= \frac{26}{2\cdot \frac{26\cdot25}{2}+26 }\\ &= \frac{1}{25+1} = \frac{1}{26} \end{align*}

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.

Solution: After \(5\) steps we can get to: \begin{array}{c|c} x & \text{ways} \\ \hline 5 & 1 \text { - go positive every time}\\ 4 & 0 \\ 3 & \binom{5}{1} \text { - go positive every time but 1} \\ 2 &0 \\ \hline & 6 \end{array} Therefore there are \(\frac{6}{2^5} = \frac{3}{16}\) ways to get to \(\{2,3,4,5\}\) After \(6\) steps we can get to: \begin{array}{c|c} x & \text{ways} \\ \hline 5 & 0 \\ 4 & \binom{6}{1} \text { - go positive every time but 1}\\ 3 & 0 \\ 2 & \binom{6}{2} - \text{ - go positive every time but 2} \\ \hline & 21 \end{array} Therefore there are \(\frac{21}{2^6} = \frac{21}{64}\) ways to get to \(\{2,3,4,5\}\) After \(2k\) steps we can reach \(2\) or \(4\). To get to \(2\) we must take \(k+1\) positive steps and \(k-1\) negative steps, ie \(\binom{2k}{k-1}\). To get to \(4\) we must take \(k+2\) positive steps and \(k-2\) negative steps, ie \(\binom{2k}{k-2}\) Therefore there are \(\binom{2k+1}{k-1}\) routes, ie a probability of \(\frac{1}{2^{2k}} \binom{2k+1}{k-1}\) After \(2k+1\) steps we can reach \(3\) or \(5\). To get to \(3\) we must take \(k+2\) positive steps and \(k-1\) negative steps, ie \(\binom{2k+1}{k-1}\). To get to \(5\) we must take \(k+3\) positive steps and \(k-2\) negative steps, ie \(\binom{2k+1}{k-2}\) Therefore there are \(\binom{2k+2}{k-1}\) routes, ie a probability of \(\frac{1}{2^{2k+1}} \binom{2k+2}{k-1}\) To find the maximum of \(P(s)\) notice that \begin{align*} && \frac{P(2k+1)}{P(2k)} &= \frac12 \frac{\binom{2k+2}{k-1}}{\binom{2k+1}{k-1}} \\ &&&= \frac12 \frac{(2k+2)!(k-1)!(k+2)!}{(2k+1)!(k-1)!(k+3)!} \\ &&&= \frac12 \frac{2k+2}{k+3} = \frac{k+1}{k+3} < 1 \end{align*} So we should only look at the even terms. \begin{align*} && \frac{P(2k+2)}{P(2k)} &= \frac14 \frac{\binom{2k+3}{k}}{\binom{2k+1}{k-1}} \\ &&&= \frac14 \frac{(2k+3)!(k-1)!(k+2)!}{(2k+1)!k!(k+3)!} \\ &&&= \frac14 \frac{(2k+3)(2k+2)}{k(k+3)} \\ &&&= \frac{(2k+3)(k+1)}{2k(k+3)} \geq 1 \\ \Leftrightarrow && (2k+3)(k+1) &\geq 2k(k+3) \\ \Leftrightarrow && 2k^2+5k+3 &\geq 2k^2+6k \\ \Leftrightarrow && 3 &\geq k \\ \end{align*} Therefore the maximum is when \(s = 2\cdot 3\) or \(s = 2\cdot 4\) which we computed earlier to be \(\frac{21}{64}\)

Solution: \begin{align*} \mathbb{P}(\text{run out reading for toffee on } N\text{th occassion}) &= \binom{N-1}{n}p^nq^{N-1-n}p \end{align*} Since out of the first \(N-1\) times, we need to choose toffee \(n\) times, and then choose it again for the \(N\)th time. Therefore: \begin{align*} \mathbb{P}(\text{reaching for toffee} | \text{run out on }N\text{th occassion}) &= \frac{\mathbb{P}(\text{reaching for toffee and run out on }N\text{th occassion})}{\mathbb{P}(\text{reaching for toffee and run out on }N\text{th occassion}) + \mathbb{P}(\text{reaching for mint and run out on }N\text{th occassion})} \\ &= \frac{ \binom{N-1}{n}p^nq^{N-1-n}p}{ \binom{N-1}{n}p^nq^{N-1-n}p + \binom{N-1}{m}q^mp^{N-1-m}q} \\ &= \frac{ \binom{N-1}{n}}{ \binom{N-1}{n} + \binom{N-1}{m} \l \frac{q}{p} \r^{m+ n+ 2-N}} \end{align*} Some conclusions we can draw from this are: As \(p \to 1, q \to 0\), the probability they were reaching for a Toffee tends to \(1\). (And vice versa). If \(p = q\), then the probability is: \begin{align*} \frac{ \binom{N-1}{n}}{ \binom{N-1}{n} + \binom{N-1}{m} } \end{align*} Since \(n+1 \leq N \leq n+m+1\) where \(n \geq m\) we can notice that: \begin{align*} \text{if } N = m + n + 1 && \binom{m+n+1 - 1}{n} &= \binom{m+n+1 - 1}{m} & \text{ so } \mathbb{P} = \frac12 \\ \text{if } N = n+k && \binom{n+k-1}{n} &< \binom{n+k-1}{m} & \text{ so } \mathbb{P} < \frac12 \\ \end{align*}

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*}

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*}