Maths Olympiad Prep

Library / /379 of 520

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it

At a chess tournament, every pair of contestants played each other at most once. If any two con-
testants, AA and BB, failed to play each other, then exactly two other contestants, CC and DD, played
against both AA and BB during the tournament. Moreover, no 44 contestants played exactly 55 games
between them. Prove that every contestant played the same number of games.

Proposed by Mirko Petrushevski

Solution

1. Graph Representation:
- Represent the chess tournament as a graph G G where each vertex represents a contestant.
- Draw an edge between two vertices if the corresponding contestants did not play each other.

2. Properties of the Graph:
- Given that if any two contestants A A and B B did not play each other, there exist exactly two other contestants C C and D D who played against both A A and B B . This implies that for every edge AB AB in G G , there is a pair of vertices C C and D D such that AC,AD,BC, AC, AD, BC, and BD BD are not edges in G G . We call such pairs of edges conjugates.\textit{conjugates}.
- Additionally, no four contestants played exactly five games among them, which implies that there are no subgraphs isomorphic to K4 K_4 minus one edge.

3. Maximal Degree Argument:
- Consider a vertex X X with maximal degree in G G .
- Let U U be a neighbor of X X and Z Z be an endpoint of the conjugate edge of XU XU .
- For each neighbor Y Y of X X , either ZY ZY is an edge, or Z Z is the endpoint of the conjugate edge of XY XY . This implies that Z Z has at least as many neighbors as X X , so Z Z also has maximal degree.

4. Breadth-First Search (BFS) Argument:
- Using BFS, we can show that every vertex in the graph has the same degree.
- Start from a vertex with maximal degree and explore its neighbors. By the previous argument, all these neighbors must also have maximal degree.
- Continue this process iteratively. Since the graph is connected, every vertex will be reached, and each will be shown to have the same degree.

5. Conclusion:
- Since every vertex in the graph has the same degree, it follows that every contestant played the same number of games.

\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.