
Problem 2. In a football tournament there are $n$ teams, with $n \geq 4$, and each pair of teams meets exactly once. Suppose that, at the end of the tournament, the final scores form an arithmetic sequence where each team scores 1 more point than the following team on the scoreboard. Determine the maximum possible score of the lowest scoring team, assuming usual scoring for football games (where the winner of a game gets 3 points, the loser 0 points, and if there is a tie both teams get 1 point).


Solution. Note that the total number of games equals the number of different pairings, that is, $n(n-1) / 2$. Suppose the lowest scoring team ends with $k$ points. Then the total score for all teams is

$$
k+(k+1)+\cdots+(k+n-1)=n k+\frac{(n-1) n}{2}
$$

Some games must end in a tie, for otherwise, all team scores would be a multiple of 3 and cannot be 1 point apart. Since the total score of a tie is only 2 points compared to 3 points if one of the teams wins, we therefore know that

$$
n k+\frac{(n-1) n}{2}<3 \cdot \frac{n(n-1)}{2}
$$

so $n k<n(n-1)$, and hence $k<n-1$. It follows that the lowest scoring team can score no more than $n-2$ points.

We now show by induction that it is indeed possible for the lowest scoring team to score $n-2$ points.

The following scoreboard shows this is possible for $n=4$ :

| - | 3 | 1 | 1 | 5 |
| :---: | :---: | :---: | :---: | :---: |
| 0 | - | 1 | 3 | 4 |
| 1 | 1 | - | 1 | 3 |
| 1 | 0 | 1 | - | 2 |

Now suppose we have a scoreboard for $n$ teams labelled $T_{n-2}, \ldots, T_{2 n-3}$, where team $T_{i}$ scores $i$ points. Keep the results among these teams unchanged while adding one more team.

Write $n=3 q+r$ with $r \in\{1,-1,0\}$, and let the new team tie with just one of the original teams, lose against $q$ teams, and win against the rest of them. The new team thus wins $n-1-q$ games, and gets $1+3(n-1-q)=3 n-2-3 q=2 n-2+r$ points.

Moreover, we arrange for the $q$ teams which win against the new team to form an arithmetic sequence $T_{j}, T_{j+3}, \ldots, T_{j+3(q-1)}=T_{j+n-r-3}$, so that each of them, itself having gained three points, fills the slot vacated by the next one.

(i) If $r=1$, then let the new team tie with team $T_{n-2}$ and lose to each of the teams $T_{n-1}, T_{n+2}, \ldots, T_{n-1+n-r-3}=T_{2 n-5}$.

Team $T_{n-2}$ now has $n-1$ points and takes the place vacated by $T_{n-1}$. At the other end, $T_{2 n-5}$ now has $2 n-2$ points, just one more than the previous top team $T_{2 n-3}$. And the new team has $2 n-2+r=2 n-1$ points, becoming the new top team. The teams now have all scores from $n-1$ up to $2 n-1$.

(ii) If $r=-1$, then let the new team tie with team $T_{2 n-3}$ and lose to each of the teams $T_{n-2}, T_{n+1}, \ldots, T_{n-2+n-r-3}=T_{2 n-4}$.

The old top team $T_{2 n-3}$ now has $2 n-2$ points, and its former place is filled by the new team, which gets $2 n-2+r=2 n-3$ points. $T_{2 n-4}$ now has $2 n-1$ points and is the new top team. So again we have all scores ranging from $n-1$ up to $2 n-1$.

(iii) If $r=0$, then let the new team tie with team $T_{n-2}$ and lose to teams $T_{n-1}, T_{n+2}, \ldots, T_{n-1+n-r-3}=T_{2 n-4}$.

Team $T_{n-2}$ now has $n-1$ points and fills the slot vacated by $T_{n-1}$. At the top end, $T_{2 n-4}$ now has $2 n-1$ points, while the new team has $2 n-2+r=2 n-2$ points, and yet again we have all scores from $n-1$ to $2 n-1$.

This concludes the proof.
