Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This problem was asked in a test, couple of years ago. Looked interesting!

In a chess tournament, each pair of players plays exactly one game. No game is drawn. Suppose the $i^{th}$ player wins $a_{i}$ games and loses $b_{i}$ games. Show that $$\sum a_{i}^{2} = \sum b_{i}^{2}$$

I can't think of a better title. It would be nice in case someone comes up with a nice title.

share|improve this question
1  
This doesn't have much to do with chess! Maybe a title including the word "tournament" would be better. By the way, it's spelt "loses", not "looses". –  Hans Lundmark Oct 15 '10 at 15:31
    
Yes, tournament is a directed graph where you assign a direction between any two nodes. I will change the title to reflect that. –  Aryabhata Oct 15 '10 at 16:30
add comment

3 Answers 3

up vote 8 down vote accepted

$$\sum (a_i^2 - b_i^2) = \sum (a_i+b_i)(a_i-b_i) = (n-1) \sum (a_i-b_i) $$ $$= (n-1) \left(\sum a_i - \sum b_i\right) = (n-1)\left(\binom{n}{2} - \binom{n}{2}\right) = 0,$$ where $n$ is the total number of players. (Each player plays $n-1$ games, so $a_i+b_i = n-1$, and there are a total of $\binom{n}{2}$ games played, so $\sum a_i = \sum b_i = \binom{n}{2}$.)

share|improve this answer
add comment

Consider flipping the result of one game, say between player 1 and 2.

Then $\sum (a_i)^2 - \sum (b_i)^2$ changes by $2(a_1 + b_1) - 2(a_2 + b_2) = 0$ as $a_i + b_i = n-1$, where $n$ is the number of players.

Thus $\sum (a_i)^2 - \sum (b_i)^2$ is the same no matter what the results and thus is same as the extreme case when the winner wins all matches, the runner up all but one etc, for which the sum is 0.

share|improve this answer
    
Very clear and intuitive. And exactly the same tactic that was used on tournament-style problem on the 2012 Putnam! –  Potato Sep 20 '13 at 2:03
    
@Potato: Thanks! –  Aryabhata Sep 20 '13 at 3:47
add comment

Let the number of wins of a random player be A, and let the number of losses of a random player be B. Then A and B have the same mean (half the number of games) and the same variance (since $B = n-A$, where n is the number of players). So $A^2$ and $B^2$ have the same expectation, which is what you want.

(Of course, if you write this out more explicitly it'll resemble Mike Spivey's answer quite closely. But this is what went through my head.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.