Kvant Math Problem 1156

There are eight teams, each playing once against every other team, so each team plays $7$ games.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m23s
Source on kvant.digital

Problem

Eight hockey teams compete against each other for a spot in the final four. (Each pair of teams plays once; a win awards two points, a draw one point, and a loss zero points.) What is the minimum number of points that guarantees a place in the final four?

Sanzhar Khadzhiev, 10th-grade student

Exploration

There are eight teams, each playing once against every other team, so each team plays $7$ games. The scoring system gives $2$ points for a win, $1$ point for a draw, and $0$ for a loss. A total of $\binom{8}{2} = 28$ games are played. The total number of points distributed in a single game is either $2$ (if one team wins) or $2$ (split as $1+1$ in case of a draw), so the total sum of points over all games is exactly $2 \cdot 28 = 56$ points.

I want to find the minimum number of points $P$ such that a team with at least $P$ points is guaranteed a top-four finish. Intuitively, I need to consider the worst-case scenario in which other teams can cluster points to push a team out of the top four. It seems plausible that $P$ is less than the maximum possible points ($14$, from $7$ wins), but greater than half of that.

If every team wins roughly half its games and loses the other half, points concentrate around $7$ or $8$. I need to consider an adversarial arrangement where one team tries to minimize another's ranking while keeping total points consistent.

A natural first guess is $9$ or $10$ points, because $8$ points could allow a situation where four other teams also reach $8$ points, pushing our team to fifth. I will test this scenario in detail in the proof.

Problem Understanding

The problem asks to determine the minimum number of points that guarantees a team a place in the top four of an eight-team round-robin tournament with a standard point system. This is a Type C problem, because we are asked to find an extremal value (the minimum guarantee).

The core difficulty is to construct the worst-case distribution of points among the eight teams that would minimize the rank of a team with a given number of points and then prove that above a certain threshold, it is impossible to be pushed below fourth place. The intuitive answer seems to be $10$ points because $9$ points can be shared among more than four teams in a way that would exclude a team with $9$ points from the top four.

Proof Architecture

Lemma 1: The total number of points distributed among all teams is $56$. This follows from $28$ games each contributing $2$ points.

Lemma 2: A team with $10$ points cannot be in the bottom four. Sketch: If a team had $10$ points and four other teams also had at least $10$ points, the sum of points would be at least $5 \cdot 10 = 50$, leaving only $6$ points for the remaining three teams. It is impossible to assign these $6$ points over $3$ teams without violating the total number of games each team plays.

Lemma 3: A team with $9$ points can be forced into fifth place. Sketch: Construct a configuration where four teams accumulate $10$ points or more while the fifth team has $9$ points, showing that $9$ points does not guarantee a top-four finish.

The hardest step is Lemma 2 because it requires ensuring no clever distribution of draws could reduce the top team's points while keeping a team at $10$ below fourth. Lemma 3 is simpler as it requires only one concrete example.

Solution

Each team plays $7$ games, so a team can score at most $14$ points. There are $28$ games in total. Each game contributes $2$ points to the total, giving a total of $56$ points in the tournament.

Suppose a team $A$ has $10$ points. Assume for contradiction that it does not finish in the top four. Then at least four teams have strictly more than $10$ points. The minimum points for each of these four teams is $11$, giving a total of at least $4 \cdot 11 = 44$ points. Including team $A$'s $10$ points gives $54$ points distributed among five teams. The remaining three teams then share $56 - 54 = 2$ points.

The maximum a single team can score is $14$ points, and each of the remaining three teams has played seven games. To score a total of $2$ points among three teams over seven rounds each, the distribution must involve draws or losses against the top five teams. However, consider that the four top teams must have each played against each other, giving at least $\binom{4}{2} = 6$ games among themselves. These six games contribute $12$ points among the four teams. Since each top team must reach at least $11$ points, the sum of points required among the four top teams is at least $44$, as noted. These $44$ points already account for all games among themselves ($12$ points), so the remaining $32$ points must come from games against the other four teams, which is impossible because each of the remaining four teams plays only $4$ games against the top four teams, contributing at most $4 \cdot 2 = 8$ points.

This contradiction shows that it is impossible for a team with $10$ points to be outside the top four.

Next, we show that $9$ points are insufficient. Construct the following scenario. Let four teams win five games and lose two games among themselves in a balanced way, accumulating $10$ points each. Let the fifth team win four games, draw one, and lose two, giving $9$ points. The remaining three teams can have lower totals. In this configuration, the team with $9$ points finishes fifth. Therefore $9$ points do not guarantee a top-four finish.

Thus, the minimum number of points guaranteeing a top-four finish is $10$.

$\boxed{10}$

Verification of Key Steps

For Lemma 2, the crucial step is the counting of points among the four supposed top teams. We compute the points from their internal games as $6$ games giving $12$ points and note that each must reach at least $11$ points, leaving $32$ points to be distributed among games with the bottom four teams. Each bottom team can contribute at most $2$ points per game, and there are only $4 \cdot 4 = 16$ points available in these games. This confirms the impossibility.

For Lemma 3, we explicitly construct a distribution with four teams having $10$ points and a fifth team with $9$ points. Checking the sums and the number of games ensures that the configuration is valid and that the team with $9$ points indeed finishes fifth. This avoids assuming symmetry or uniformity.

Both verifications confirm that the minimum guarantee threshold is correct.

Alternative Approaches

One could attempt a combinatorial optimization approach by systematically distributing points in all possible ways and checking for the fifth-place threshold. This approach is more computationally intensive and less transparent. The main approach is preferable because it relies on simple inequalities on sums of points and clear constraints from the number of games, producing a rigorous argument without exhaustive enumeration.