ashani.dasgupta@cheenta.com

Round robin tournament

Problem : Suppose there are \[ {k}\] teams playing a round robin tournament; that is, each team plays against all the other teams and no game ends in a draw.Suppose the \[ {i^{th}}\] team loses \[ {l_{i}}\] games and wins \[ {w_{i}}\] games.Show that

\[ {{\displaystyle}{\sum_{i=1}^{k}{l_i^{2}}}}\] = \[ {{\displaystyle}{\sum_{i=1}^{k}{w_i^{2}}}}\]

Solution : Each team plays exactly one match against each other team.

Consider the expression \[ \displaystyle{\sum_{i=1}^{k} l_i^{2} – {w_i^2} = \sum_{i=1}^{k}(l_i + w_i)(l_i – w_i) } \]

Since each team plays exactly k-1 matches and no match ends in a draw, hence number of wins plus numbers of loses of a particular team is k-1 (that is the number of matches it has played). In other words \[ l_i + w_i = k-1 \] for all i (from 1 to k).

Hence

\[ \displaystyle{\sum_{i=1}^{k} l_i^{2} – {w_i^2} } \]
\[ \displaystyle{= \sum_{i=1}^{k}(l_i + w_i)(l_i – w_i) } \]
\[ \displaystyle{= \sum_{i=1}^{k}(k-1)(l_i – w_i) } \]
\[ \displaystyle{= (k-1)\left( \sum_{i=1}^{k} l_i – \sum_{i=1}^{k} w_i\right) } \]

But \[ \displaystyle{ \sum_{i=1}^{k} l_i = \sum_{i=1}^{k} w_i } \] (as total number of loses = total number of matches = total number of wins; as each match results in a win or lose of some one)

Hence \[ \displaystyle{= (k-1)\left( \sum_{i=1}^{k} l_i – \sum_{i=1}^{k} w_i\right) = (k-1) \times 0 = 0 } \]

Therefore \[ \displaystyle{\sum_{i=1}^{k} l_i^{2} – {w_i^2} = 0 } \] implying \[ {{\displaystyle}{\sum_{i=1}^{k}{l_i^{2}}}}\] = \[ {{\displaystyle}{\sum_{i=1}^{k}{w_i^{2}}}}\]

Proved.


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *