Optimal schedule for a soccer tournament

Question

Motivation. This weekend, my children took part in a soccer tournament consisting of $n$ teams, each of which playing once against every other team. As there was only one soccer field, the schedule consisted of $n\choose 2$ games played one after the other. Some teams protested that they were scheduled to play in two successive games. Others complained about having to wait for a long time between two successive games.

This made me wonder whether an optimal schedule could be constructed, meaning that for every team the intervals between successive games are almost the same.

Formalisation. If $n$ is a positive integer, let $\text{enum}(n) := \{0, \ldots, n-1\}$. If $X$ is a set, let $[X]^2 := \big\{\{x,y\}: x\neq y\in X\big\}$. For the following, we interpret $n$ as the number of teams, $\text{enum}(n)$ as the set of teams, $[\text{enum}(n)]^2$ as the collection of all team pairings, and $\text{enum}{n\choose 2}$ as the set of game slots. A schedule for $n$ teams is a bijection $$\sigma: \text{enum}{n\choose 2} \to [\text{enum}(n)]^2.$$

For any team $t\in\text{enum}(n)$, the set of game slots of $t$ is defined as $$\text{sl}(t) = \sigma^{-1}\big(\{g \in [\text{enum}(n)]^2 : t\in g\}\big).$$

Note that $\text{sl}(t) \subseteq \text{enum}{n\choose 2}$ consists of exactly $n-1$: the slots of games that $t$ is playing, and $t$ plays against everyone else exactly once. We order $\text{sl}(t)$ recursively by setting

• $\text{sl}(t)_0 = \min \text{sl}(t)$, and
• $\text{sl}(t)_{k} = \min\{x\in \text{sl}(t): x > \text{sl}(t)_{k-1}$ for all $k\in \{1,\ldots,n-1\}$.

So $\text{sl}(t)_k$ is the slot number of game $k$ of team $t$.

Let $\text{ovmin}(\sigma)$ be the overall minimum of all breaks that any team has in consecutive games, that is $\text{ovmin}(\sigma) = \min\{\text{sl}(t)_{k+1} - \text{sl}(t)_k: t\in\text{enum}(n), 0\leq k < n-1\}.$ The overall maximum of all breaks that any team has in consecutive games, $\text{ovmax}(\sigma)$ is defined by replacing $\min$ by $\max$.

Let $\text{BESTMIN}(n)$ be the maximum of all $\text{ovmin}(\sigma)$ where $\sigma$ ranges over all schedules $\sigma: \text{enum}{n\choose 2} \to [\text{enum}(n)]^2$ and let $\text{BESTMAX}(n)$ be the minimum of all $\text{ovmax}(\sigma)$ where $\sigma$ ranges over all schedules $\sigma: \text{enum}{n\choose 2} \to [\text{enum}(n)]^2$. (So, both terms are typical min-max definitions.)

Question. Given a positive integer $n$, is there a "super schedule" $\sigma^*: \text{enum}{n\choose 2} \to [\text{enum}(n)]^2$ such that $\text{ovmin}(\sigma^*) = \text{BESTMIN}(n)$ and $\text{ovmax}(\sigma^*) = \text{BESTMAX}(n)$?

Also, it would be of interest to get estimations (or exact values) for $\text{BESTMIN}(n)$ and $\text{BESTMAX}(n)$ in terms of $n$, but this is not necessary for the acceptance of the answer.

Acknowledgement. Thanks to @LeechLattice for spotting an error in the definition of $\text{ovmax}(\cdot)$.

Answer 1

Here is a streamlined description of the optimal strategies that have been found. In both strategies, there is a team that plays a special role -- call them $x$ -- and the other teams are numbered modulo $n-1$.

---

With $n=2k$ teams: We play $2k-1$ rounds of $k$ games each. In the $i$-th round, the games are $$(x,i), (i-1,i+1), (i-2, i+2), \ldots, (i-k+1, i+k-1).$$ Team $x$ always waits $k$ games between playing; every other team either waits $k-1$ or $k+1$ games. (Here I mean the difference between time slots: If team $x$ plays at time $t$, then they play again at time $t+k$.)

---

With $n=2k+1$ teams: We play $2k$ rounds which are alternately "long" ($k+1$ games) and "short" ($k$ games), starting with a long round. In the $i$-th long round, the games are $$(x,i), (i+1,i-1), (i+2, i-2), \ldots, (i+k-1, i-k+1), (i+k, x).$$ In the $i$-th short round, the games are $$(i,i+1), (i-1, i+2), (i-2, i+3), \ldots, (i-k+1, i+k).$$ Every wait is either $k$ or $k+1$ games.

---

I wish I had time to make some animated graphics of these. I'd put players $1$ through $n-1$ around a circle and $x$ at the center, and draw lines between the pairs as they occur.

Answer 2

Here is a first attempt, for others to improve on. For simplicity, I'll take $n=2k+1$ to be odd. We index the teams by integers modulo $n$.

We'll schedule $n$ rounds of $k$ games each. In the $j$-th round, the games (in order) are $$ \{ j+1, j-1 \},\ \{ j+2, j-2 \},\ \{ j+3, j-3 \},\ \ldots,\ \{ j+k, j-k \}$$ and team $j$ sits out.

The longest break between games is $2k$ games (team $j$ plays the first game in the $(j-1)$-st round, sits out the $j$-th round and plays the first game in the $(j+1)$-st round). All the other breaks are either $k-1$ or $k+1$ games. So the ratio between longest break and shortest break is $\approx 2$.

I bet we can get that ratio down to $1+o(1)$. What solutions have other people found?

Answer 3

For even $n=2k$ there is such a super-schedule. As Peter Taylor wrote, it should be easy to prove that $BESTMIN \le k-1$ and $BESTMAX\ge k+1$. Writing down a schedule with $ovmin=k-1$ and $ovmax=k+1$ thus means, that it is a super-schedule and that both bounds are sharp.

The idea is to think of it as a chess tournament, e.g. think of a long table (say from left to right) with $k$ chess boards. The idea is that one fixed player always stays at the leftmost board, while the other players (after each round is finished) move to their left around the table (and skip the fixed player). In this model the games are played simultaneously, while in the question they are played sequentially (e.g. we have only one board).

Thus we start from left to right and play the leftmost game first until that round is finished and we start with the next round.

Let us now figure out how long the breaks are. If a player sits at board $m$ in some round, then in the next round he sits at one of the boards $m-1,m,m+1$. Thus he always has a break of $k-1,k,k+1$ games. This shows that $ovmin=k-1$ and $ovmax=k+1$ and thus this is a super-schedule and the bounds are sharp.

The case of odd n remains open.

Answer 4

Disclaimer: this is a partial answer which expands on some comments I've made on the question and on the earlier answers.

Bounds

Theorem: $\textrm{BESTMIN}(n) \le \lfloor \frac{n-1}{2}\rfloor$
Proof: consider first the case of odd $n = 2k+1$. Suppose $\text{ovmin}(\sigma) > k$. Then no team can play twice in the first $k+1$ matches. But that requires $2k+2$ distinct teams, giving a contradiction. For even $n$ the argument is similar. If $n=2k$ and $\text{ovmin}(\sigma) \ge k$ then no team can play twice in the first $k$ matches, and the only teams which can play in the $(k+1)$st match (and that only if $\text{ovmin}(\sigma) = k$) are the teams which already met in the first match, violating the tournament structure and giving a contradiction. $\blacksquare$

Conjecture: $\textrm{BESTMAX}(n) = \lfloor \frac{n+2}{2} \rfloor$
An argument along similar lines doesn't seem so promising. Consider the case $n = 2k+1$. Suppose $\text{ovmax}(\sigma) \le k$. Then a team whose first match has index $i$ must play all $n-1$ matches by the end of match $i + (n-2)\operatorname{ovmax}(\sigma) \le i + (n-2)k$. Note that there are a total of $\frac{n(n-1)}2 = nk$ matches. So the two teams which play in the first match can't play in the last $2k-1$ matches. But can we have $O(\sqrt n)$ teams play the first $n$ matches, $O(\sqrt n)$ teams play the last $n$ matches, and nullify the problem?

---

Tournament for odd number of teams

I claim that the following slot assignment gives a tournament for $n = 2k+1$ teams with $\text{ovmin}(\sigma) = k$ and $\text{ovmax}(\sigma) = k+1$. This is optimal for $\text{ovmin}$ and for $\text{ovmax} - \text{ovmin}$.

$$\text{sl}(t) = \begin{cases} \{ \lfloor \frac{jn}2 \rfloor : 0 \le j < n-1 \} & \textrm{if } t = 0 \\ \{\frac{t-1}2 + j(k+1) - \max(0, j+t-n) : 0 \le j < n-1 \} & \textrm{if } t \equiv 1 \pmod 2 \\ \{\frac t2 + jk + \max(0, j-t): 0 \le j < n - 1\} & \textrm{if } 2 \le t \wedge t \equiv 0 \pmod 2 \\ \end{cases}$$

The slots can be seen to stay in the range $[0, nk-1]$ so by the pigeonhole principle it suffices to show (a) that each pair of teams meets and (b) that each slot is used at most twice.

Absent a more elegant idea, (a) can be done by case analysis. I present a simple table without proofs: the proof of each case is straightforward.

$$\begin{array}[8]{cccccccc} t & u & \text{Condition} & & & & & \\ 0 & 1 & & \operatorname{sl}(t)[0] & = & \operatorname{sl}(u)[0] & = & 0 \\ 0 & 2m+1 & m > 0 & \operatorname{sl}(t)[n-u+1] & = & \operatorname{sl}(u)[n-u] & = & \frac{n(n-u+1)-1}{2} \\ 0 & 2m & m > 0 & \operatorname{sl}(t)[u] & = & \operatorname{sl}(u)[u] & = & mn \\ 2\ell + 1 & 2m+1 & m > \ell & \operatorname{sl}(t)[n - \ell - m - 1] & = & \operatorname{sl}(u)[n - \ell - m - 1] & = & (n - \ell - m - 1)(k+1) + \ell \\ 2\ell + 1 & 2m & m < \ell & \operatorname{sl}(t)[n - \ell + m - 1] & = & \operatorname{sl}(u)[n - \ell + m - 1] & = & (n - \ell + m - 1)(k+1) - m \\ 2\ell + 1 & 2m & m \ge \ell & \operatorname{sl}(t)[m - \ell] & = & \operatorname{sl}(u)[m - \ell] & = & m + (m - \ell)k \\ 2\ell & 2m & m > \ell & \operatorname{sl}(t)[m+\ell] & = & \operatorname{sl}(u)[m+\ell] & = & m + (m+\ell)k \\ \end{array}$$

I think (b) could be shown by a further pairwise case analysis, but I suspect that someone else will be able to spot a more elegant reformulation of the tournament which renders it considerably less tedious, so I'm posting as a partial answer.