Problems

---

Solution:

1. \(ACB\) is not a complete tournament since no-one has won two matches.
2. \(ABB\) is not a possible complete tournament since it implies \(B\) won game 2, which is between \(A\) (winner of game 1) and \(C\) (referee of game 1).
3. \(ACBB\) is a valid tournament, \(A\) beat \(B\), then \(C\) beat \(A\), then \(B\) beat \(C\) and finally \(B\) beat \(A\) to win.

After the first game there is always someone playing for the tournament, so for there to be no result after 5 games, 4 games must have gone against the leader, so the probability is \(\frac{1}{2^4} = \frac{1}{16}\). If \(A\) wins their first game, they can either win in two games (WW) or in five games (WLRWW). The probability of this is \(\frac14 + \frac1{16} = \frac{5}{16}\). Similarly \(B\) has exactly the same chance as \(A\) since everything about them is symmetric, ie a probability of \(\frac5{16}\) of winning. Since there is a \(\frac{15}{16}\) chance the tournament is decided after 5 games, the remaining \(\frac{5}{16}\) must be \(C\)'s chance of winning. After the first game is played, there's \(3\) states for each player. King (about to win if they win, becomes Ref if they lose), Challenger (needs to win to become king) and Ref (who becomes Challenger if Challenger wins). \begin{align*} \P(\text{King wins}) &= \frac{1}{2} + \frac{1}{2}\P(\text{Ref wins})\\ \P(\text{Challenger wins}) &= \frac{1}{2} \P(\text{King wins}) \\ \P(\text{Ref wins}) &= \frac{1}{2} \P(\text{Challenger wins}) \\ \end{align*} \(p_K = \frac12 + \frac12 (\frac12 \frac12 p_K) \Rightarrow \frac78 p_K = \frac12 \Rightarrow p_K = \frac47, p_C = \frac27, p_R = \frac17\). \(A\) has \(\frac12\) of being king, \(\frac12\) of being ref after the first match, so \(\frac12 \frac47 + \frac12 \frac17 = \frac{5}{14}\). Similarly \(B\) has \(\frac5{14}\) chance of winning, but unfortunately \(C\) must be the challenger after the first match and only has \(\frac27 = \frac4{14}\) chances of winning.

---

Solution:

1. The vote is will now be \(60(1-\alpha)\) for, \(60\alpha\) against and \(X \sim B(40, \frac12)\) at random between those. For a majority, they need \(60(1-\alpha) + X > 50\), ie \(\P(X > 60\alpha - 10) \geq 0.8\). Using a normal approximation to the binomial, we need \(X \approx N(20, 10)\), so \begin{align*} \P(X > 60 \alpha - 10) &= 1- \P(X \leq 60 \alpha - 10) \\ &\approx 1 - \P(\sqrt{10}Z+20 \leq 60\alpha - 10.5) \\ &\approx 1 - \P(Z \leq \frac{60\alpha - 30.5}{\sqrt{10}}) \end{align*} If we want this to be less than \(0.2\) we need \( \frac{60\alpha - 30.5}{\sqrt{10}} < -0.8416 \Rightarrow \alpha < 0.4639\). This would correspond to 27 or fewer exiles or 33 or more remaining preservatives. [Actual computations using Binomial distribution shows we should expect at least 17 to randomly join 20% of the time, so 34 preservatives are required]

---

Solution:

1. \begin{align*} && p_n &= \mathrm{P}(A\leqslant k\mbox{ and }B\geqslant1-k) \\ &&&= \mathrm{P}(A\leqslant k) +\P(B\geqslant1-k) - \mathrm{P}(A\leqslant k\mbox{ or }B\geqslant1-k)\\ &&&= 1-\mathrm{P}(A\geq k) +1-\P(B \leq 1-k) - \l 1- \mathrm{P}(A\geq k\mbox{ and }B\leq 1-k)\r\\ &&&= 1 - \P(X_i \geq k) - \P(X_i \leq 1-k) + \P(k \leq X_i \leq 1-k) \\ &&&= 1 - k^n - (1-k)^n + (1-2k)^n \end{align*} Therefore as \(n \to \infty\) \(p_n \to 1\), since \(k, (1-k), (1-2k)\) are all between \(0\) and \(1\) and so their powers will tend to \(0\).
2. Let \(N = 4\,000\,000\). The probability exactly one person wins is \(Np(1-p)^{N-1}\). The probability exactly two people win is \(\binom{N}{2} p^2 (1-p)^{N-2}\). We wish to maximise the sum of these probabilities. To find this maximum, differentiate wrt \(p\). \begin{align*} \frac{\d}{\d p} : && \small N(1-p)^{N-1}-N(N-1)p(1-p)^{N-2} + N(N-1)p(1-p)^{N-2} - \frac12 N(N-1)(N-2)p^2(1-p)^{N-3} \\ &&= N(1-p)^{N-3} \l (1-p)^2 - \frac12(N-1)(N-2)p^2\r \\ \Rightarrow && \frac{(1-p)}{p} = \sqrt{\frac{(N-1)(N-2)}{2}} \\ \Rightarrow && p = \frac{1}{1+ \sqrt{\frac{(N-1)(N-2)}{2}}} \end{align*} This will be a maximum, since this is an increasing function at \(p=0\) and decreasing at \(p=1\) and there's only one stationary point. Note that \(p > \frac{\sqrt{2}}{(N-2)}\) and \(p < \frac{\sqrt{2}}{N-1+\sqrt{2}} < \frac{\sqrt{2}}{N}\) and so: \begin{align*} Np(1-p)^{N-1} &< \sqrt{2}(1-\frac{\sqrt{2}}{N-2})^{N-1} \\ &\approx \sqrt{2} e^{-\sqrt{2}} \end{align*} \begin{align*} \frac{N(N-1)}{2}p^2(1-p)^{N-2} &<(1-\frac{\sqrt{2}}{N-2})^{N-1} \\ &\approx e^{-\sqrt{2}} \end{align*} Alternatively, we can use a Poisson approximation. The number of winners is \(B(N, p)\) where we are hoping \(np\) is small but not zero. Therefore it's reasonable to approximation \(B(N,p)\) by \(Po(Np)\). (Call this value \(\lambda\)). Then we wish to maximise: \begin{align*} && p &= e^{-\lambda} \l \lambda + \frac{\lambda^2}{2} \r \\ &&&= e^{-\lambda} \lambda \l 1+ \frac{\lambda}{2} \r \\ \Rightarrow && \ln p &= -\lambda + \ln \lambda + \ln(1+\frac12 \lambda) \\ \frac{\d}{\d \lambda}: && \frac{p'}{p} &= -1 + \frac{1}{\lambda} + \frac{1}{2+\lambda} \\ &&&= \frac{-(2+\lambda)\lambda+2+2\lambda}{\lambda(2+\lambda)} \\ &&&= \frac{2-\lambda^2}{\lambda(2+\lambda)} \\ \Rightarrow && \lambda &= \sqrt{2} \end{align*} \begin{align*} \frac{\sqrt{2}+1}{e^{\sqrt{2}}} &< \frac{\sqrt{2}+1}{1+\sqrt{2}+1+\frac{1}{3}\sqrt{2}+\frac{1}{6}} \\ &= \frac{30\sqrt{2}-18}{41} \end{align*} Either way, we find we want to estimate \(e^{-\sqrt{2}}(1+\sqrt{2})\)