1
$\begingroup$

Suppose, there are $k$ teams playing a round robin tournament that is, each team plays against all other teams and no game ends in a draw. Suppose the $ith$ team loses $l_i$ games and wins $w_i$ games. Show that $$\sum _{i=1}^k l_i^2=\sum_{i=1}^kw_i^2.$$

My solution goes like this:

There are $k$ teams and thus, each team plays $k-1$ games. If the $ith$ wins $w_i$ times, then, $l_i+w_i=k-1$, which implies $ \sum_{i=1}^k(l_i+w_i)=\frac{k(k-1)}{2}.$ Now, $w_i+l_i=k-1$ and thus, $w_i^2-l_i^2=(w_i-l_i)(w_i+l_i)$, due to which $$\sum_{i=1}^k (w_i^2-l_i^2)=\sum_{i=1}^k(l_i+w_i)(w_i-l_i)=(k-1)\sum_{i=1}^k(w_i-l_i).$$ As, no game ends in a tie, thus, $\sum_{i=1}^kw_i=\sum_{i=1}^kl_i. $ More, specifically, the reason can also be stated in a beautiful manner. I got to know, about this reasoning from @leslie townes. The reason goes like this : For each game, we give, one apple to the winning team, and one orange, to the loosing team. No game, ends in a tie. So, for each game, we need to giveaway one apple and one orange. When, the tournament ends, the number of apples given away is equal to the number of oranges which implies the total number of winning matches is equal to the total number of loosing matches. Thus, $\sum_{i=1}^kw_i=\sum_{i=1}^kl_i,$ whence, we conclude, $$\sum_{i=1}^k (w_i^2-l_i^2)=0\implies \sum _{i=1}^k l_i^2=\sum_{i=1}^kw_i^2.$$

Is the solution correct? If not, where is it going wrong?

$\endgroup$
2

2 Answers 2

3
$\begingroup$

Write $\sum _{i=1}^k l_i^2=\sum_{i=1}^kw_i^2$ as $\sum _{i=1}^k l_i^2-\sum_{i=1}^kw_i^2=0$. This is what we want to prove.

Then, we evaluate $\sum_{i} (w_i+l_i)(w_i-l_i)$, which is the same as $\sum _{i=1}^k l_i^2-\sum_{i=1}^kw_i^2$.

Since there are no draws, $l_i+w_i=k-1$ for each $i$. Furthermore, $w_i-l_i$ would be the team's score in a $-1,1$ scoring system.

Can you take it from here?

$\endgroup$
6
  • $\begingroup$ Thanks a lot! But can uou please elaborate upon this ," Furthermore, $w_i−l_i$ would be the teams score in a $−1,1$ scoring system.". I dont get how, $\sum (w_i-l_i)=0$ ? $\endgroup$
    – Arthur
    Mar 15 at 7:20
  • $\begingroup$ Whenever a team wins, some other team loses. You sum over all games. The scores should be zero. $\endgroup$ Mar 15 at 7:21
  • $\begingroup$ Ok... If I am not mistaken then: Whenever, a team wins we assign +1 score to it and the team which looses we assign -1 score to it. Thus, "for every +1 there is a -1 score," and hence, when we add all the scores, we get $0$ , right? If this is the case, I still dont get, how is $\sum (w_i-l_i)=0$ ? $\endgroup$
    – Arthur
    Mar 15 at 7:26
  • $\begingroup$ What is $w_i-l_i$? It is the score of the team at the end of the tourney. Why? It would get +1 for each win and -1 for each loss. It would get $w_i$ +1s and $l_i$ -1s, which gives $w_i-l_i$. $\endgroup$ Mar 15 at 7:29
  • $\begingroup$ We just have to prove that the sum of scores of the teams in the tourney at the end of the tourney is $0$. $\endgroup$ Mar 15 at 7:31
2
$\begingroup$

The end of your proof, you write, "If only we could prove the total number of losses is $(k-1)/2$".

Well, there are $k$ teams, so $k(k-1)$ results were created, half of which were wins and half of which were losses by symmetry. Hence, $\sum l_i = k(k-1)/2$. But then, we have by your algebra, that $\sum l_i = (k-1)/2$.

Hence, we would have $k(k-1)/2=(k-1)/2$, and hence $k = 1$, contradicting the statement "Let $k$ be any positive integer". Therefore, the logic in your proof is incorrect, or you made a non-reversible step somewhere.

To see a valid proof, see Umesh answer above ^^.

$\endgroup$
3
  • $\begingroup$ Is my solution , correct now ? $\endgroup$
    – Arthur
    Mar 15 at 7:49
  • $\begingroup$ @Franklin No, it is incorrect. $\endgroup$
    – Snared
    Mar 15 at 7:56
  • $\begingroup$ check my answer for how many results were created and recount $\endgroup$
    – Snared
    Mar 15 at 7:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .