In a soccer league with $2020$ teams every two team have played exactly once and no game have lead to a draw. The participating teams are ordered first by their points (3 points for a win, 1 point for a draw, 0 points for a loss) then by their goal difference (goals scored minus goals against) in a normal soccer table. Is it possible for the goal difference in such table to be strictly increasing from the top to the bottom? Proposed by Abolfazl Asadi
Problem
Source: Iranian Combinatorics Olympiad 2020 P1
Tags: combinatorics
27.04.2020 17:41
Assume that such configuration is possible. Since there's no draw, if a team wins in $x$ matches, its total points are $3x+(2019-x)=2x+2019$. No two teams can win the same number of matches, because then the ordering of their goal differences would not satisfy the condition. So, the team that finish $k$th place wins in exactly $2020-k$ matches. So, the worst team always lose, and so its goal difference is negative, which implies the goal difference of every team is negative. This is obviously impossible.
18.02.2021 06:54
ThE-dArK-lOrD wrote: Assume that such configuration is possible. Since there's no draw, if a team wins in $x$ matches, its total points are $3x+(2019-x)=2x+2019$. No two teams can win the same number of matches, because then the ordering of their goal differences would not satisfy the condition. So, the team that finish $k$th place wins in exactly $2020-k$ matches. So, the worst team always lose, and so its goal difference is negative, which implies the goal difference of every team is negative. This is obviously impossible. but why its total points are $3x+(2019-x)=2x+2019$?, the loss give 0 points
26.07.2021 06:31
We solve this generally for $n$ teams. we will order the table with number of wins instead of points. Note that a team that loses all games will have a negative GD, and a team that wins all games will have a positive GD, which is a contradiction. Thus, we cannot have both a degree 0 and degree $n-1$ team. Then, by pigeonhole, we have two teams with the same number of wins, which is a contradiction because comparison between these two teams is based on GD.
28.07.2021 17:41
A nice problem. Also note that in the official statement of the problem, there was nothing about "1 point for a draw," but that is irrelevant. FTSOC, assume the problem is false. Notice that no two teams can have the same exact score, as then when they were sorted, the ordering would already be wrong(the one on the top would have the greatest GD). Therefore, by pigeonhole, we know that the teams must have won $2019, 2018, \cdots, 1,0$ games respectively. However, the team that won $0$ games would be at the bottom, and because their GD in each game is negative, their GD as a whole is negative. Then by our assumption that the problem is false, all of the scores of teams must be negative. But this is impossible, because the sum of the goal differences of all the teams must be $0$, so we are done.