Kvant Math Problem 971
Consider a tournament of $8$ volleyball teams where each team plays every other team exactly once.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m37s
Source on kvant.digital
Problem
Eight volleyball teams played a single-round tournament (each team played every other team exactly once). Prove that it is possible to select four teams $A$, $B$, $C$, $D$ such that $A$ defeated $B$, $C$, and $D$, $B$ defeated $C$ and $D$, and $C$ defeated $D$.
A. T. Ukrainets
Exploration
Consider a tournament of $8$ volleyball teams where each team plays every other team exactly once. Each match has a winner, so the tournament is represented as a complete directed graph on $8$ vertices, where an edge from $X$ to $Y$ indicates that $X$ defeated $Y$. The problem asks for four teams $A$, $B$, $C$, $D$ such that $A$ beats $B$, $C$, $D$; $B$ beats $C$, $D$; and $C$ beats $D$. This is equivalent to finding a transitive $4$-vertex subgraph (a chain of victories) in the tournament.
Small cases suggest that the top-ranked team must have at least three victories because it beats more than half the teams. The structure is reminiscent of the Erdős–Moser theorem on transitive subtournaments: every tournament on $n$ vertices contains a transitive subtournament of size at least $\lceil \log_2 n \rceil$. Here, $\lceil \log_2 8 \rceil = 3$, but we need size $4$. It is necessary to exploit the pigeonhole principle: in an 8-team tournament, there exists a team with at least $4$ victories, and careful selection among these wins can produce the desired chain.
A risky point is assuming without verification that the team with the highest number of wins can always produce the required $4$-chain; explicit case analysis is needed to ensure no configuration breaks the claim.
Problem Understanding
The problem requires selecting four teams $A$, $B$, $C$, $D$ from a single-round tournament of eight teams such that $A$ defeats $B$, $C$, $D$; $B$ defeats $C$ and $D$; and $C$ defeats $D$. This is a Type B problem, "Prove that [statement]". The core difficulty is to ensure that regardless of the results among the eight teams, such a chain of victories exists. The challenge arises from arbitrary tournament outcomes, particularly in avoiding cycles that might prevent a linear ordering among four teams. The intuitive reason the statement should hold is that in any sufficiently large tournament, there are always four teams that can be linearly ordered by victories, due to combinatorial constraints on win counts.
Proof Architecture
Lemma 1: In a tournament of $8$ teams, there exists a team with at least $4$ wins. This is true because the sum of all wins is $\binom{8}{2} = 28$, and if every team had at most $3$ wins, the sum would be at most $24$, a contradiction.
Lemma 2: Let $A$ be a team with at least $4$ wins, and let $S$ be the set of teams it defeated. Then either $S$ contains a team $B$ that defeated at least two other teams in $S$, or $S$ can be arranged to form the desired chain directly. The reasoning relies on the fact that $|S| \ge 4$, and in a four-element set with all pairwise results, there must exist a chain of length $3$.
Lemma 3: Any tournament on four vertices contains a transitive $4$-chain if the degree conditions from Lemma 2 hold. The hardest part is analyzing the combinatorial possibilities within the set $S$ to guarantee the existence of the required subgraph.
The proof strategy is to identify a team with many victories and examine the subset of teams it defeated, then iteratively choose the next team in the chain using degree considerations to ensure the transitive property.
Solution
Label the eight teams $T_1, T_2, \dots, T_8$. Represent the tournament as a directed graph where an edge from $X$ to $Y$ indicates $X$ defeated $Y$. The total number of matches is $\binom{8}{2} = 28$, so the sum of all teams' wins equals $28$.
By the pigeonhole principle, at least one team must have at least $\lceil 28/8 \rceil = 4$ victories. Let $A$ be such a team, and let $S$ denote the set of teams $A$ defeated. Then $|S| \ge 4$. Consider any four-element subset of $S$, say $S_0 = {B, C, D, E}$. Within the four-team tournament induced by $S_0$, there are $6$ matches. A classical combinatorial fact asserts that every tournament on four vertices contains a transitive three-element chain.
Select three teams from $S_0$ forming a transitive chain in the induced tournament. Denote these teams as $B, C, D$ such that $B$ beats $C$ and $D$, and $C$ beats $D$. Since $A$ defeats all teams in $S$, in particular $A$ defeats $B$, $C$, and $D$.
Hence, the four teams $A$, $B$, $C$, $D$ satisfy the required property: $A$ defeats $B$, $C$, $D$; $B$ defeats $C$ and $D$; $C$ defeats $D$. The selection guarantees that the transitive chain exists regardless of the internal outcomes among the defeated teams.
This completes the proof.
∎
Verification of Key Steps
Step 1: Ensuring a team has at least $4$ victories. The sum of all wins is $28$, and if every team had at most $3$ wins, the total sum would be at most $24$, which is impossible. Verification is complete.
Step 2: Existence of a transitive three-element chain within any four-team tournament. Any tournament on four vertices has $6$ directed edges. Consider any team with maximal outdegree; it must beat at least two other teams. This team can serve as $B$, the next highest in the chain, while the team it beats can be $C$, and the one $C$ beats is $D$. All possible configurations yield a transitive triple, confirming robustness.
Alternative Approaches
One alternative is to consider the tournament as a graph and apply the Erdős–Moser theorem, which guarantees a transitive subtournament of size at least $\lceil \log_2 8 \rceil = 3$, and then carefully extend this to size $4$ by examining the outdegrees of the highest-ranked team. Another method is a purely combinatorial argument using the Pigeonhole Principle on victories and defeats among the top four teams, systematically excluding cycles. The main approach is preferable because it is constructive and immediately produces the required four teams without enumerating all $8$-team configurations.