1
$\begingroup$

There are n teams playing in a round-robin tournament. Then prove that

a.the sum of the number of wins by each team is equal to the sum of the number of losses by each team.

b.the sum of the squares of the number of wins by each team is equal to the sum of the squares of the number of losses by each team.

Any help will be truly appreciated.

$\endgroup$
  • $\begingroup$ Whats round robin tournament $\endgroup$ – Archis Welankar Feb 29 '16 at 15:45
  • $\begingroup$ Every team plays with all the other teams but only once. $\endgroup$ – jyoti prokash roy Feb 29 '16 at 15:47
  • $\begingroup$ Thats very easy consider team as one participant if n participants win then n participant of course lose and from here squaring both you get b whats making you think to help graph $\endgroup$ – Archis Welankar Feb 29 '16 at 15:49
  • $\begingroup$ no its not like that $\endgroup$ – jyoti prokash roy Feb 29 '16 at 15:52
  • $\begingroup$ math.lafayette.edu/files/2010/03/PGF13Set5.pdf $\endgroup$ – jyoti prokash roy Feb 29 '16 at 15:55
3
$\begingroup$

To put it in graph-theoretic terms, let $G$ be the directed graph on the vertex set $[n]=\{1,\ldots,n\}$ such that $\langle k,\ell\rangle$ is an edge of $G$ if and only if team $k$ beat team $\ell$. Then the number of wins by team $k$ is $\operatorname{out-deg}(k)$, the number of losses by team $k$ is $\operatorname{in-deg}(k)$, and of course

$$\operatorname{out-deg}(k)+\operatorname{in-deg}(k)=n-1\tag{1}$$

for each $k\in[n]$.

The first problem is simply to prove that the sum of the out-degrees of the vertices is equal to the sum of the in-degrees, which is very straightforward. The second is more interesting: you’re to show that

$$\sum_{k=1}^n\big(\operatorname{out-deg}(k)\big)^2=\sum_{k=1}^n\big(\operatorname{in-deg}(k)\big)^2\;.$$

This is equivalent to showing that

$$\sum_{k=1}^n\big(\operatorname{out-deg}(k)\big)^2-\sum_{k=1}^n\big(\operatorname{in-deg}(k)\big)^2=0$$

or, equivalently, that

$$\sum_{k=1}^n\Big(\big(\operatorname{out-deg}(k)\big)^2-\big(\operatorname{in-deg}(k)\big)^2\Big)=0\;.\tag{2}$$

Now factor the difference of two squares inside the summation $(2)$ and make use of $(1)$ and the first problem to get the desired result.

$\endgroup$
1
$\begingroup$

Every game has exactly one winner and one loser, so the sum of wins equals the the total number of games, as does the sum of losses.

For b, you can do it using a bit of combinatorics. Since it is a round robin tournament we know the total number of games is $n$ choose $2$, which is $\frac{n(n-1)}{2}$. Also if we denote the number of wins and losses of team $i$ by $w_i$ and $l_i$ respectively then $w_i + l_i = n-1$ because each team plays $n-1$ games. Therefore $w_i = n-1 - l_i$ and we can square both sides, sum over $i$, and do some cancellation.

I don't know how to do this using graph theory though.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.