Problems

---

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

---

Solution:

1. \(\,\) \begin{align*} && 3 &= 2^2 - 1^2 \\ && 5 &= 3^2 - 2^2 \\ && 8 &= 3^2 - 1^2 \\ && 16 &= 5^2 - 3^2 \end{align*}
2. Suppose \(n = 2k+1\), then \(n = (k+1)^2 - k^2\)
3. Suppose \(n = 4k\) then \(n = (2k+1)^2 - (2k-1)^2\)
4. All squares leave a remainder of \(0\) or \(1\) on division by \(4\). Therefore the difference can leave a remainder of \(0\), \(1\), \(-1 \equiv 3\), none of which are \(2\).
5. Suppose \(n = pq = a^2 - b^2\) with \(a > b\) ie \((a-b)(a+b) = pq\). Since \(p\) is prime, \(p \mid (a-b)\) or \(p \mid (a+b)\). Similarly for \(q\). Suppose also (wlog) that \(p > q\) Since the factors of \(pq\) are \(1, p, q, pq\) then \(a-b = 1, p\) (which are two possibilities) and \(a+b = pq, q\), ie \(a = \frac{1+pq}{2}, \frac{p+q}{2}\) and \(b = \frac{pq-1}{2}, \frac{p-q}{2}\) \begin{align*} && pq &= \left ( \frac{1+pq}{2} \right)^2- \left ( \frac{1-pq}{2} \right)^2 \\ &&&= \left ( \frac{p+q}{2} \right)^2- \left ( \frac{p-q}{2} \right)^2 \\ \end{align*} Where everything is an integer since \(p\) and \(q\) are odd. If we have \(p > 2\) and \(q = 2\) then \(p\) is odd and the number has the form \(4k+2\) which cannot be expressed as the difference of two squares.
6. \(675 = 3^3 \cdot 5^2\), each factor pair of \(675\) will lead to a different solution of \(675 = a^2-b^2\), since we will have an equation \(a-b = X, a+b = Y\) where \(X, Y\) are both odd. Therefore there are as many solution as (half) the number of factors, ie \(4 \times 3 = 12\)

---

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

---

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

---

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.

---

Solution: In order to receive \(n\) marks over the two papers, where \(m < n \leq 2m\) the student must receive \(k\) and \(n-k\) marks in each paper. Since \(n > m\), \(n-k\) is a valid mark when \(n-k \leq m\) ie when \(n-m\leq k\), therefore the probability is: \begin{align*} \sum_{k = n-m}^m \mathbb{P}(\text{scores }k\text{ and }n-k) &= \sum_{k=n-m}^m \frac{1}{(m+1)^2} \\ &= \frac{m-(n-m-1)}{(m+1)^2} \\ &= \frac{2m-n+1}{(m+1)^2} \end{align*} If \(0 \leq n \leq m\) then we need \(n-k\) marks in the second paper to be positive, ie \(n-k \geq 0 \Rightarrow n \geq k\), so \begin{align*} \sum_{k = 0}^n \mathbb{P}(\text{scores }k\text{ and }n-k) &= \sum_{k = 0}^n \frac{1}{(m+1)^2} \\ &= \frac{n+1}{(m+1)^2} \end{align*} On the first paper, they can score any number of marks, since \(n > m\), so we must have: \begin{align*} \sum_{k=0}^m \mathbb{P}(\text{scores }k\text{ and }n-k) &= \frac{1}{m+1} \sum_{k=0}^m \mathbb{P}(\text{scores }n-k\text{ on second papers}) \\ &= \frac{1}{m+1}\l \sum_{k=0}^{n-m} \frac{2m-(n-k)+1}{(m+1)^2} +\sum_{k=n-m+1}^m \frac{n-k+1}{(m+1)^2}\r \end{align*}