Maths Olympiad Prep

Library / /329 of 520

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it

At a two-round volleyball tournament participated 99 teams. Each played a match at home and a match away. Each team won exactly half of their home matches and exactly half of their away matches. Prove that one of the teams beat another team twice.

Proposed by M. Antipov

Solution

1. Assume the contrary: Suppose that no team beats another team twice. This implies that for any pair of teams, each team wins exactly one match against the other. Therefore, each pair of teams has a 1-1 record.

2. Count the total number of home wins: Each team plays 98 matches (49 at home and 49 away). Since each team wins exactly half of their home matches, each team wins 24.5 home matches. However, since the number of matches must be an integer, this is not possible. Therefore, we need to reconsider the counting method.

3. Recalculate the total number of home wins correctly: Each team wins exactly half of their home matches, which means each team wins 24 home matches (since 49/2 = 24.5, and we round down to the nearest integer). Therefore, the total number of home wins across all teams is:
99×24=2376 99 \times 24 = 2376

4. Count the total number of matches: Each team plays 98 matches, so the total number of matches played in the tournament is:
99×982=4851 \frac{99 \times 98}{2} = 4851
(since each match is counted twice, once for each team).

5. Parity argument: The total number of home wins must be even because each match has one home win and one away win. However, the total number of home wins calculated is 2376, which is even. This does not immediately lead to a contradiction.

6. Reconsider the problem statement: Since each team wins exactly half of their home matches and half of their away matches, and there are 99 teams, the total number of wins (both home and away) for each team is 49.5, which is not possible since the number of wins must be an integer.

7. Correct the counting method: Each team wins exactly half of their home matches and half of their away matches. Therefore, each team wins 24 home matches and 24 away matches, making a total of 48 wins per team. The total number of wins in the tournament is:
99×48=4752 99 \times 48 = 4752

8. Contradiction: Since each match results in one win, the total number of wins must be equal to the total number of matches, which is 4851. However, we calculated 4752 wins, which is a contradiction.

Therefore, our initial assumption that no team beats another team twice must be false. Hence, there must be at least one team that beats another team twice.

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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