Question

A round-robin tournament is played amongst \[n\]-players. Each pair of players plays one game that culminates in a win for one player. A win earns \[1\] point; a loss \[0\] points. At the culmination of the tournament player \[i\] has \[{a_i}\] points \[\left( {0 \leqslant {a_i} \leqslant n - 1} \right)\]. Suppose that \[b = \left( {{b_1},{b_2},{b_3}, \ldots \ldots ,{b_n}} \right)\] is a given \[n\]-tuple of non-negative integers with \[{b_1} \leqslant {b_2} \leqslant \ldots \leqslant {b_n}\].. Prove that the \[n\]-tuple \[b\] could have arisen from a round-robin tournament as the set of final scores iff
I.\[\sum\limits_{i = 1}^n {{b_i}} = \left( {\begin{array}{*{20}{c}}
  n \\
  2
\end{array}} \right)\]
II.\[\sum\limits_{i = 1}^k {{b_i} \geqslant \left( {\begin{array}{*{20}{c}}
  k \\
  2
\end{array}} \right)} \] for \[1 \leqslant k \leqslant n\]

Answer 1

Hint: Here, in the question, we have been given that a round-robin tournament is played. And we have given some conditions for the same such as points-structure. And at last we have been given equations and are asked to prove which of the given equations holds true as a set of final scores of the round-robin tournament. We will first understand how the round robin tournament is played and how it’s structured.

Complete step-by-step answer:
A round-robin tournament is a tournament where each player/team plays against every other player/team exactly once.
And since there are \[n\] players, every player plays \[\left( {n - 1} \right)\] matches. That is why a player can have a maximum of \[\left( {n - 1} \right)\] points as given in the question.
Now we will understand the calculation of total points of a tournament.
Player \[1\] plays \[\left( {n - 1} \right)\] matches, player \[2\] similarly plays \[\left( {n - 1} \right)\] matches, but the total matches played by player \[1\& 2\] will be \[\left[ {\left( {n - 1} \right) + \left( {n - 1} \right) - 1} \right]\] because there is one match common between both the players. Similarly, player \[3\] will play \[\left( {n - 1} \right)\] matches in total but the sum of matches played by all three players will be \[\left[ {\left( {n - 1} \right) + \left[ {\left( {n - 1} \right) - 1} \right] + \left[ {\left( {n - 1} \right) - 2} \right]} \right]\]. And moving so on, the additional matches played by the \[{n^{th}}\] player will be \[0\] as all the matches has already been counted till \[{\left( {n - 1} \right)^{th}}\] player.
So, if we count the total number of matches in a tournament, it will be a series of sum of first \[\left( {n - 1} \right)\] natural numbers.
Now we know that,
Sum of first \[n\] natural numbers = \[\dfrac{{n\left( {n + 1} \right)}}{2}\]
Therefore, Sum of first \[\left( {n - 1} \right)\] natural numbers = \[\dfrac{{n\left( {n - 1} \right)}}{2}\]
Hence, the total number of matches played in tournament = \[\dfrac{{n\left( {n - 1} \right)}}{2}\] and assuming that there is no tie, there will be a winner and a loser in each match, therefore,
Total number of wins = Total number of points scored in tournament = \[\dfrac{{n\left( {n - 1} \right)}}{2}\].
Taking first option, \[\sum\limits_{i = 1}^n {{b_i}} = \left( {\begin{array}{*{20}{c}}
  n \\
  2
\end{array}} \right)\]
L.H.S. = \[\sum\limits_{i = 1}^n {{b_i}} \]
Since \[{b_i}\] represents the points scored by each player, the sum of points scored by each player will be equal to the total points scored in a tournament.
Therefore, L.H.S. = \[\dfrac{{n\left( {n - 1} \right)}}{2}\]
Now, R.H.S. = \[\left( {\begin{array}{*{20}{c}}
  n \\
  2
\end{array}} \right)\]
\[
   = {}^n{C_2} \\
   = \dfrac{{n!}}{{2!\left( {n - 2} \right)!}} \\
   = \dfrac{{n\left( {n - 1} \right)\left( {n - 2} \right)!}}{{2(n - 2)!}} \\
   = \dfrac{{n\left( {n - 1} \right)}}{2} \\
 \]
= L.H.S.
Taking second option, \[\sum\limits_{i = 1}^k {{b_i} \geqslant \left( {\begin{array}{*{20}{c}}
  k \\
  2
\end{array}} \right)} \]
We have L.H.S. = \[\sum\limits_{i = 1}^k {{b_i}} \] for \[1 \leqslant k \leqslant n\]
Clearly, it represents the sum of points scored by \[k\] players where \[1 \leqslant k \leqslant n\]. And also, we are given \[{b_1} \leqslant {b_2} \leqslant \ldots \leqslant {b_n}\] which further implies that the sum will be greater than or equal to the sum of first \[\left( {k - 1} \right)\] natural numbers.
Now, Sum of first \[\left( {k - 1} \right)\] natural numbers = \[\dfrac{{k\left( {k - 1} \right)}}{2}\]
Therefore, \[\sum\limits_{i = 1}^k {{b_i} \geqslant \left( {\begin{array}{*{20}{c}}
  k \\
  2
\end{array}} \right)} \]

Note: Whenever we face such types of questions, it is important that we understand the meaning and structure of round-robin tournaments. Whatever we have discussed here as a theory part is actually what we use for combination. A match is played between two players and we select the number of ways \[n\] players can play a match irrespective of any order.
If still getting confused, one can easily understand it numerically by assuming any natural value of \[n\].