Olympiad Maths Prep

Track / Stage 6 / 387 of 400 #1387 of 2000

Problem 1387

National olympiad, first round
Combinatorics Difficulty 6.9 Prove it

nn teams participated in a basketball tournament. Each team has played with each team exactly one game. There was no tie. If in the end of the tournament the ii-th team has xix_{i} wins and yiy_{i} loses (1in)(1\leq i \leq n) prove that:
i=1nxi2=i=1nyi2\sum_{i=1}^{n} {x_{i}}^2=\sum_{i=1}^{n} {y_{i}}^2

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

1. Each team plays with every other team exactly once, so the total number of games each team plays is n1 n - 1 . Therefore, for each team i i , we have:
xi+yi=n1 x_i + y_i = n - 1
where xi x_i is the number of wins and yi y_i is the number of losses for team i i .

2. We need to prove that:
i=1nxi2=i=1nyi2 \sum_{i=1}^{n} x_i^2 = \sum_{i=1}^{n} y_i^2

3. Start by considering the expression:
i=1n(xi2yi2) \sum_{i=1}^{n} (x_i^2 - y_i^2)

4. Using the identity a2b2=(a+b)(ab) a^2 - b^2 = (a + b)(a - b) , we can rewrite the sum as:
i=1n(xi2yi2)=i=1n(xi+yi)(xiyi) \sum_{i=1}^{n} (x_i^2 - y_i^2) = \sum_{i=1}^{n} (x_i + y_i)(x_i - y_i)

5. Since xi+yi=n1 x_i + y_i = n - 1 for all i i , we can factor out n1 n - 1 from the sum:
i=1n(xi+yi)(xiyi)=(n1)i=1n(xiyi) \sum_{i=1}^{n} (x_i + y_i)(x_i - y_i) = (n - 1) \sum_{i=1}^{n} (x_i - y_i)

6. Next, observe that the total number of wins in the tournament is equal to the total number of losses because each game results in one win and one loss. Therefore:
i=1nxi=i=1nyi \sum_{i=1}^{n} x_i = \sum_{i=1}^{n} y_i

7. This implies:
i=1n(xiyi)=i=1nxii=1nyi=0 \sum_{i=1}^{n} (x_i - y_i) = \sum_{i=1}^{n} x_i - \sum_{i=1}^{n} y_i = 0

8. Substituting this back into our earlier expression, we get:
(n1)i=1n(xiyi)=(n1)0=0 (n - 1) \sum_{i=1}^{n} (x_i - y_i) = (n - 1) \cdot 0 = 0

9. Therefore:
i=1n(xi2yi2)=0 \sum_{i=1}^{n} (x_i^2 - y_i^2) = 0

10. This implies:
i=1nxi2=i=1nyi2 \sum_{i=1}^{n} x_i^2 = \sum_{i=1}^{n} y_i^2

\blacksquare

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.