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)$.
Best Answer
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.