Question

A round-robin tournament of $n$contestants is a tournament in which each of the $\left(\frac{n}{2}\right)$pairs of contestants play each other exactly once, with the outcome of any play being that one of the contestants wins and the other loses. For a fixed integer $k,k<n$, a question of interest is whether it is possible that the tournament outcome is such that for every set of $k$players, there is a player who beat each member of that set. Show that if

$\left(\begin{array}{l}n\\ k\end{array}\right){\left[1-{\left(\frac{1}{2}\right)}^k\right]}^{n-k}<1$

then such an outcome is possible.

Hint: Suppose that the results of the games are independent and that each game is equally likely to be won by either contestant. Number the $\left(\begin{array}{l}n\\ k\end{array}\right)$sets of $k$contestants, and let $B_i$denote the event that no contestant beat all of the $k$players in the $i^{th}$set. Then use Boole's inequality to bound $P\left(\underset{i}{\cup } B_i\right)$.

Short answer

Demonstrate that following inequality imply,$P\left(A_k^c\right)<1$

Step-by-step solution

Given data

For $\left(\frac{n}{2}\right)$individual matches, $n$similarly competent players compete against one another.

$A_k$- for every $k$individuals chosen, at most the another player outperformed it all.

$B_l$- There is no mutual winner among the $k$participants inside the $l-\text{th}$set, $l=1,2,\dots ,\left(\begin{array}{l}n\\ k\end{array}\right)$

$\frac{1}{2}$is the possibility of particular player succeeding in such a specific game.

Show if

$\left(\begin{array}{l}n\\ 2\end{array}\right){\left[1-{\left(\frac{1}{2}\right)}^k\right]}^{n-k}<1$

then

$P\left(A_k\right)>0$

Boole's inequality

At minimum single $B_i$existed when $A_k$didn't take place, and inversely, it is:

$A_k^c=\underset{l=1}{\overset{\left(\begin{array}{l}n\\ k\end{array}\right)}{\cup }} B_l$

Boole's inequalities, which is established from the formula combining inclusion as well as exclusion conditions for whichever series of incidents, in this case $B_1,B_2,\dots B_l$.

$P\left(\underset{l=1}{\overset{\left(\begin{array}{l}n\\ k\end{array}\right)}{\cup }} B_l\right)\le \sum _{l=1}^{\left(\begin{array}{l}n\\ k\end{array}\right)} P\left(B_l\right)$

The probability of outcomes $i=1,2,3,\dots ,\left(\begin{array}{l}n\\ k\end{array}\right)$were same since they're balanced.

$P\left(A_k^c\right)=P\left(\begin{array}{l}\left(\begin{array}{c}n\\ k\end{array}\right)\\ \cup \\ l=1\end{array}\right)\le \left(\begin{array}{l}n\\ k\end{array}\right)P\left(B_1\right)$ $\left(1\right)$

Its possibility that particular player wins every match against $k$competitors watched was

${\left(\frac{1}{2}\right)}^k$

Prove PAkc<1

Because the activities are self-contained.

It should occur for each one of remaining $n-k$participants. These events were self-contained since they were determined by outcomes of assorted games and so the people participating. Against by observed $k$, chance that neither of any $n-k$competitors succeeded seems to be:

$P\left(B_1\right)={\left[1-{\left(\frac{1}{2}\right)}^k\right]}^{n-k}$

Put the equation $\left(1\right)$,

$P\left(A_k^c\right)\le \left(\begin{array}{l}n\\ k\end{array}\right){\left[1-{\left(\frac{1}{2}\right)}^k\right]}^n$

So, if

$\left(\begin{array}{l}n\\ 2\end{array}\right){\left[1-{\left(\frac{1}{2}\right)}^k\right]}^{n-k}<1$

Then role="math" localid="1649481274549" $P\left(A_k^c\right)<1$and which is equal to $P\left(A_k\right)>0$