\(% Differentiation % https://tex.stackexchange.com/a/60546/ \newcommand{\Diff}{\mathop{}\!\mathrm{d}} \newcommand{\DiffFrac}[2]{\frac{\Diff #1}{\Diff #2}} \newcommand{\DiffOp}[1]{\frac{\Diff}{\Diff #1}} \newcommand{\Ndiff}[1]{\mathop{}\!\mathrm{d}^{#1}} \newcommand{\NdiffFrac}[3]{\frac{\Ndiff{#1} #2}{\Diff {#3}^{#1}}} \newcommand{\NdiffOp}[2]{\frac{\Ndiff{#1}}{\Diff {#2}^{#1}}} % Evaluation \newcommand{\LEvalAt}[2]{\left.#1\right\vert_{#2}} \newcommand{\SqEvalAt}[2]{\left[#1\right]_{#2}} % Epsilon & Phi \renewcommand{\epsilon}{\varepsilon} \renewcommand{\phi}{\varphi} % Sets \newcommand{\NN}{\mathbb{N}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\PP}{\mathbb{P}} \renewcommand{\emptyset}{\varnothing} % Probabililty \DeclareMathOperator{\Cov}{Cov} \DeclareMathOperator{\Corr}{Corr} \DeclareMathOperator{\Var}{Var} \DeclareMathOperator{\Expt}{E} \DeclareMathOperator{\Prob}{P} % Distribution \DeclareMathOperator{\Binomial}{B} \DeclareMathOperator{\Poisson}{Po} \DeclareMathOperator{\Normal}{N} \DeclareMathOperator{\Exponential}{Exp} \DeclareMathOperator{\Geometric}{Geo} \DeclareMathOperator{\Uniform}{U} % Complex Numbers \DeclareMathOperator{\im}{Im} \DeclareMathOperator{\re}{Re} % Missing Trigonometric & Hyperbolic functions \DeclareMathOperator{\arccot}{arccot} \DeclareMathOperator{\arcsec}{arcsec} \DeclareMathOperator{\arccsc}{arccsc} \DeclareMathOperator{\sech}{sech} \DeclareMathOperator{\csch}{csch} \DeclareMathOperator{\arsinh}{arsinh} \DeclareMathOperator{\arcosh}{arcosh} \DeclareMathOperator{\artanh}{artanh} \DeclareMathOperator{\arcoth}{arcoth} \DeclareMathOperator{\arsech}{arsech} \DeclareMathOperator{\arcsch}{arcsch} % UK Notation \DeclareMathOperator{\cosec}{cosec} \DeclareMathOperator{\arccosec}{arccosec} \DeclareMathOperator{\cosech}{cosech} \DeclareMathOperator{\arcosech}{arcosech} % Paired Delimiters \DeclarePairedDelimiter{\ceil}{\lceil}{\rceil} \DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor} \DeclarePairedDelimiter{\abs}{\lvert}{\rvert} \DeclarePairedDelimiter{\ang}{\langle}{\rangle} % Vectors \newcommand{\vect}[1]{\mathbf{#1}} \newcommand{\bvect}[1]{\overrightarrow{#1}} % https://tex.stackexchange.com/a/28213 % \DeclareMathSymbol{\ii}{\mathalpha}{letters}{"10} % \DeclareMathSymbol{\jj}{\mathalpha}{letters}{"11} % \newcommand{\ihat}{\vect{\hat{\ii}}} % \newcommand{\jhat}{\vect{\hat{\jj}}} \newcommand{\ihat}{\textbf{\^{ı}}} \newcommand{\jhat}{\textbf{\^{ȷ}}} \newcommand{\khat}{\vect{\hat{k}}} % Other Functions \DeclareMathOperator{\sgn}{sgn} \DeclareMathOperator{\tr}{tr} % Other Math Symbols \DeclareMathOperator{\modulo}{mod} \newcommand{\divides}{\mid} \newcommand{\notdivides}{\nmid} \newcommand{\LHS}{\text{LHS}} \newcommand{\RHS}{\text{RHS}} \newcommand{\degree}{^{\circ}}\)
Let \(X_i\) be the number that the \(i\)th player receives, and let Ada be the first player. We have \begin {align*} \Prob (X_1 = a, X_2 > X_1, X_3 > X_1, \cdots , X_k > X_1) & = \Prob (X_1 = a, X_2 > a, X_3 > a, \cdots , X_k > a) \\ & = \Prob (X_1 = a) \Prob (X_2 > a) \Prob (X_3 > a) \cdots \Prob (X_k > a) \\ & = \frac {1}{n} \cdot \frac {n - a}{n} \cdot \frac {n - a}{n} \cdots \frac {n - a}{n} \\ & = \frac {(n - a)^{k - 1}}{n^k}. \end {align*}
Hence, the probability of Ada winning this is \begin {align*} \Prob (X_2 > X_1, X_3 > X_1, \cdots , X_k > X_1) & = \sum _{a = 1}^{n - 1} \Prob (X_1 = a, X_2 > X_1, X_3 > X_1, \cdots , X_k > X_1) \\ & = \sum _{a = 1}^{n - 1} \frac {(n - a)^{k - 1}}{n^k} \\ & = \frac {1}{n^k} \sum _{a = 1}^{n - 1} a^{k - 1}, \end {align*}
and the probability of there being a winner is the sum of the probabilities of each player winning, which are all equal to the probability of Ada winning by symmetry, and hence is equal to \[ k \cdot \frac {1}{n^k} \sum _{a = 1}^{n - 1} a^{k - 1} = \frac {k}{n^k} \sum _{a = 1}^{n - 1} a^{k - 1}. \]
If \(k = 4\), then this probability is given by \begin {align*} \Prob & = \frac {4}{n^4} \sum _{a = 1}^{n - 1} a^3 \\ & = \frac {4}{n^4} \cdot \frac {(n - 1)^2 n^2}{4} \\ & = \frac {(n - 1)^2}{n^2}, \end {align*}
precisely as desired.
Similarly, let \(X_i\) be the number that the \(i\)th player receives, and let Ada be the first player, and Bob be the second player. We have \begin {align*} & \phantom {=} \Prob (X_1 = a, X_2 = a + d + 1, X_1 < X_3 < X_2, \cdots , X_1 < X_k < X_2) \\ & = \Prob (X_1 = a, X_2 = a + d + 1, a < X_3 < a + d + 1, \cdots , a < X_k < a + d + 1) \\ & = \Prob (X_1 = a) \Prob (X_2 = a + d + 1) \Prob (a < X_3 < a + d + 1) \cdots \Prob (a < X_k < a + d + 1) \\ & = \frac {1}{n} \cdot \frac {1}{n} \cdot \frac {d}{n} \cdots \frac {d}{n} \\ & = \frac {d^{k - 2}}{n^k}. \end {align*}
Hence, the probability that both Ada and Bob winning this is \begin {align*} & \phantom {=} \Prob (X_1 < X_3 < X_2, \cdots , X_1 < X_k < X_2) \\ & = \sum _{d = 1}^{n - 2} \sum _{a = 1}^{n - d - 1} \Prob (X_1 = a, X_2 = a + d + 1, X_1 < X_3 < X_2, \cdots , X_1 < X_k < X_2) \\ & = \sum _{d = 1}^{n - 2} \sum _{a = 1}^{n - d - 1} \frac {d^{k - 2}}{n^k} \\ & = \sum _{d = 1}^{n - 2} \frac {(n - d - 1) d^{k - 2}}{n^k} \\ & = \frac {1}{n^k} \sum _{d = 1}^{n - 2} (n - d - 1) d^{k - 2} \\ & = \frac {1}{n^k} \left [(n - 1) \sum _{d = 1}^{n - 2} d^{k - 2} - \sum _{d = 1}^{n - 2} d^{k - 1}\right ]. \end {align*}
Hence, the probability that there are two winners in this game is the sum of the probabilities of each ordered pair of players winning (since there is one winning by having a bigger number, and one winning by having a smaller number), and hence is equal to \[ 2 \cdot \binom {k}{2} \cdot \frac {1}{n^k} \left [(n - 1) \sum _{d = 1}^{n - 2} d^{k - 2} - \sum _{d = 1}^{n - 2} d^{k - 1}\right ]. \]
When \(k = 4\), the probability is \begin {align*} \Prob & = 2 \cdot \binom {4}{2} \cdot \frac {1}{n^4} \left [(n - 1) \sum _{d = 1}^{n - 2} d^{2} - \sum _{d = 1}^{n - 2} d^{3}\right ] \\ & = 2 \dot 6 \cdot \frac {1}{n^4} \left [\frac {(n - 1) (n - 2) (n - 1) (2n - 3)}{6} - \frac {(n - 2)^2 (n - 1)^2}{4}\right ] \\ & = 12 \cdot \frac {1}{n^4} \cdot (n - 1)^2 (n - 2) \left [\frac {2 (2n - 3) - 3 (n - 2)}{12}\right ] \\ & = \frac {(n - 1)^2 (n - 2)}{n^4} \cdot n \\ & = \frac {(n - 2) (n - 1)^2}{n^3}. \end {align*}
The probability of there being a winner due to having the biggest number (denote this event as \(B\)), is the same as there being a winner due to having the lowest number (denote this event as \(L\)), which are both equal to the answer to the first part of the question: \begin {align*} \Prob (B) = \Prob (L) = \frac {(n - 1)^2}{n^2}. \end {align*}
The event of having two winners is \(B, L\) and the event of having precisely one winner is \(B, \bar {L}\) or \(L, \bar {B}\). By the inclusion-exclusion principle, the probability of having precisely one winner is given by \begin {align*} \Prob & = \Prob (B) + \Prob (L) - 2 \Prob (B, L) \\ & = 2 \cdot \frac {(n - 1)^2}{n^2} - 2 \cdot \frac {(n - 2)(n - 1)^2}{n^3} \\ & = \frac {2 (n - 1)^2}{n^3} \cdot \left [n - (n - 2)\right ] \\ & = \frac {4 (n - 1)^2}{n^3}. \end {align*}
This probability is smaller than \(\Prob (B, L)\), if and only if \begin {align*} \frac {4(n - 1)^2}{n^3} & < \frac {(n - 2) (n - 1)^2}{n^3} \\ 4 & < n - 2 \\ n & > 6, \end {align*}
and hence the minimum value of \(n\) for this is \(7\).