In a qualification football round there are six teams and each two play one versus another exactly once. No two matches are played at the same time. At every moment the difference between the number of already played matches for any two teams is $0$ or $1$. A win is worth $3$ points, a draw is worth $1$ point and a loss is worth $0$ points. Determine the smallest positive integer $n$ for which it is possible that after the $n$-th match all teams have a different number of points and each team has a non-zero number of points.
Problem
Source: Bulgaria EGMO TST 2018 Day 1 Problem 1
Tags: Tournament, combinatorics, results
31.01.2024 15:29
I hope I have not messed up stupid details. Answer: $9$ It is easier to start with finding an example for a reasonably small $n$. Suppose the first three matches are wins and play $(1, 4)$, $(2, 5)$, $(3, 6)$, so ranking after them is $1 2 3 4 5 6 | 3 3 3 0 0 0$. For the next three, make $(3,5)$ and $(2,4)$ draws and $(1,6)$ win for $1$, to get $6 4 4 1 1 0$. Now let $7$-th be a $(1,2)$ win for $2$, let $8$-th be a $(3, 4)$ draw and $9$-th be a $(5,6)$ win for $6$, to get $6 7 5 2 1 3$. Now we prove $n\leq 8$ is impossible. The results being distinct and non-zero imply their sum is at least $6 + 5 + 4 + 3 + 2 + 1 = 21$ and hence $n\geq 7$; but equality to hold requires there to be no draws (as a draw contributes a total of $2$ and not $3$ points) and at the same time to have $6$, $5$, $4$, $3$, $2$, $1$ as points, contradiction. Finally, suppose $n=8$. If $x$ is the total number of draws (so $8-x$ are win-losses), the total sum of scores is $2x + 3(8-x) = 24 - x$. Since the total is at least $21$, we have $x\leq 3$. If $x=0$, then all scores are multiples of $3$ and their sum is at least $3 + 6 + 9 + 12 + 15 + 18 > 24$, nope. If $x=1$, the only options of distinct non-zero scores are $7 6 4 3 2 1$ and $8 5 4 3 2 1$, but the $2$ comes from two draws, contradiction. If $x=2$, the only option of non-zero scores is $7 5 4 3 2 1$, but then $5$ and $2$ need at least three distinct matches of draws to have two draws in their score (as they both cannot play twice), contradiction. Hmm, but actually $x=3$ is possible... and I think the next post is the correct solution, but leaving this one for the moral.
31.01.2024 15:45
Real answer: $8$. Suppose the first three matches are wins and play $(1, 4)$, $(2, 5)$, $(3, 6)$, so ranking after them is $1 2 3 4 5 6 | 3 3 3 0 0 0$. For the next three, make $(1,6)$ a win for $1$, let $(2,4)$ and $(3,5)$ be draws, to get $6 4 4 1 1 0$. Finally, a $(3,4)$ draw and a $(5,6)$ win for $6$ leads to $6 4 5 2 1 3$. The results being distinct and non-zero imply their sum is at least $6 + 5 + 4 + 3 + 2 + 1 = 21$ and hence $n\geq 7$; but equality to hold requires there to be no draws (as a draw contributes a total of $2$ and not $3$ points) and at the same time to have $6$, $5$, $4$, $3$, $2$, $1$ as points, contradiction.