In a football championship with $2021$ teams, each team play with another exactly once. The score of the match(es) is three points to the winner, one point to both players if the match end in draw(tie) and zero point to the loser. The final of the tournament will be played by the two highest score teams. Brazil Football Club won the first match, and it has the advantage if in the final score it draws with any other team. Determine the least score such that Brazil Football Club has a chance to play the final match.
Problem
Source: Brazil National Olympiad Junior 2021 #6
Tags: combinatorics
26.10.2023 04:39
Solution. The answer is $n-1$. Let's number the teams, team 1, team 2, ..., team $n$. The OBM Football Club is team 1. Part 1. It is possible for the OBM Football Club to reach the final with $n-1$ points. Version 1 of Part 1. This is possible if team $n$ wins against all other teams, team 1 wins against team 2, team 2 wins against team 3, ..., team $n-2$ wins against team $n-1$, and team $n-1$ wins against team 1, with all other games ending in a draw. In this scenario, team $n$ earns $3(n-1)$ points, and all other teams earn $3 \cdot 1 + 1 \cdot (n-4) = n-1$ points. Therefore, OBM Football Club advances to the final based on the tiebreaker rule. Version 2 of Part 1. This is possible if team $n$ wins against all other teams, team 1 wins against team 2, team 2 wins against team 3, team 3 wins against team 1, and all other games end in a draw. In this situation, team $n$ earns $3(n-1)$ points, while teams 1, 2, and 3 earn $3 \cdot 1 + 1 \cdot (n-4) = n-1$ points, and all other teams earn $1 \cdot (n-2) = n-2$ points. Therefore, OBM Football Club advances to the final based on the tiebreaker rule. Part 2. It is impossible for OBM Football Club to reach the final with at most $n-2$ points. Version 1 of Part 2. Suppose that OBM FC qualifies for the final. Let's call the team with the highest final score, which is not OBM FC, the "leader." We'll call any team that is not the leader a "non-leader." We know that OBM FC qualifies for the final if and only if it has a final score greater than or equal to all non-leader teams. Let's count the total number of points earned by all non-leader teams. Every game between the $n-1$ non-leader teams contributes 2 points in case of a draw or 3 points if there is no draw. Therefore, all these $\frac{(n-1)(n-2)}{2}$ matches contribute at least $\frac{(n-1)(n-2)}{2}$ points. Additionally, we also know that OBM FC wins its first match. Let's consider two cases: OBM FC wins this match against the leader (case 1) or OBM FC wins this match against some non-leader (case 2). In case 1, this match was not counted before and contributes 3 points. In case 2, one of the matches already counted above contributes an additional 1 point. In both cases, we have that #(points of non-leaders) ≥ $\frac{(n-1)(n-2)}{2} + 1$. Since these points are distributed among the $n-1$ non-leader teams, by the Pigeonhole Principle, some non-leader team earns at least $n-1$ points. As OBM FC qualifies for the final, this implies that OBM FC also earned at least $n-1$ points, as desired. Version 2 of Part 2. To prove this, assume it's possible for OBM Football Club to qualify with at most $n-2$ points. Let $x$ be the number of victories by the leader, $y$ the number of draws by the leader, and $v$ the number of non-draws (wins) in all games. Since the total number of games is $n(n-1)/2$, we can conclude that $n(n-1) = 2e + 2v$ (1). Each draw contributes 2 points, and each non-draw contributes 3 points. As OBM Football Club qualifies with at most $n-2$ points, all teams except the leader have earned at most $n-2$ points. Note that the leader has earned $3x + y$ points. Therefore, considering the total points distributed, we have $2e + 3v \leq (n-2)(n-1) + (3x + y)$ (2). Also, note that the leader has played $n-1$ games. Therefore, $x + y \leq n-1$. Consequently, we can conclude that $2x + 2y \leq 2(n-1)$ (3). Lastly, OBM Football Club won its first match, and the leader won $x$ matches. Thus, we can conclude that $x + 1 \leq v$ (4). By adding equation (1) and inequalities (2), (3), and (4), we find that $n(n-1) + (2e + 3v) + (2x + 2y) + (x + 1) \leq (2e + 2v) + (n-2)(n-1) + (3x + y)$. By canceling corresponding terms, we reach $y + 1 \leq 0$, which is a contradiction.