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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s