Problem source

In this question, you may use without proof the results
\[ \sum_{i=1}^{n} i^2 = \tfrac{1}{6}n(n+1)(2n+1) \quad \text{and} \quad \sum_{i=1}^{n} i^3 = \tfrac{1}{4}n^2(n+1)^2. \]
Throughout the question, $n$ and $k$ are integers with $n \geqslant 3$ and $k \geqslant 2$.
\begin{questionparts}
\item In a game, $k$ players, including Ada, are each given a random whole number from $1$ to $n$ (that is, for each player, each of these numbers is equally likely and assigned independently of all the others). A player wins the game if they are given a smaller number than all the other players, so there may be no winner in this game.
Find an expression, in terms of $n$, $k$ and $a$, for the probability that Ada is given number $a$, where $1 \leqslant a \leqslant n-1$, and all the other players are given larger numbers. Hence show that, if $k = 4$, the probability that there is a winner in this game is
\[ \frac{(n-1)^2}{n^2}\,. \]
\item In a second game, $k$ players, including Ada and Bob, are each given a random whole number from $1$ to $n$. A player wins the game if they are given a smaller number than all the other players or if they are given a larger number than all the other players, so it is possible for there to be zero, one or two winners in this game.
Find an expression, in terms of $n$, $k$ and $d$, for the probability that Ada is given number $a$ and Bob is given number $a + d + 1$, where $1 \leqslant d \leqslant n-2$ and $1 \leqslant a \leqslant n - d - 1$, and all the other players are given numbers greater than $a$ and less than $a + d + 1$. Hence show that, if $k = 4$, the probability that there are two winners in this game is
\[ \frac{(n-2)(n-1)^2}{n^3}\,. \]
If $k = 4$, what is the minimum value of $n$ for which there are more likely to be exactly two winners than exactly one winner in this game?
\end{questionparts}

Solution source

\begin{questionparts}
\item 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}$

\item 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$
\end{questionparts}