Theorem 1. Let \(n \in \mathbf{N}, n\ge2\), then we have \[f_{\frak{s},\frak{o}}(n) = \begin{cases} \lceil \log_2(n) \rceil + 3 & \text{if } n = 2^m-1, \\ \lceil \log_2(n) \rceil + 2 & \text{otherwise.} \end{cases}\]
Menu
Chris Busenhart\(^{1}\), Norbert Hungerb\(^{1,*}\) and William Xu\(^{1}\)
\(^{1}\)Department of Mathematics, ETH Zentrum, Rämistrasse;101, 8092 Zürich, Switzerland
We consider the following variant of the round-robin scheduling problem: \(2n\) people play a number of rounds in which two opposing teams of \(n\) players are reassembled in each round. Each two players should play at least once in the same team, and each two players should play at least once in opposing teams. We provide an explicit formula for calculating the minimal numbers of rounds needed to satisfy both conditions. Moreover, we also show how one can construct the corresponding playing schedules.
Scheduling problems for sports tournaments are a broad and extensively researched field in combinatorics, operations research and combinatorial optimization. A prominent example is the round-robin tournament problem with applications, e.g., in computer science (see, e.g., [1, 2, 3 4 5, 6, 7] to mention just some of the most recent work on the subject). Another one is the traveling tournament problem (see, e.g., [8, 9, 10]). In this article we will study a variant where not fixed teams play against each other but the teams are shuffled in each round of a tournament.
We deal with the following combinatorial problem: suppose \(2n\) people are playing a sports tournament which consists of different rounds. In each round two new teams of \(n\) people are reassembled to play against each other. We would like to find a playing schedule such that the following conditions are satisfied:
The general question is: what is the minimal number \(f_{\frak{s},\frak{o}}(n)\) of rounds of the tournament so that the conditions (\(\frak{s}\)) and (\(\frak{o}\)) are satisfied and what is an optimal playing schedule? We shall give a complete answer to both questions. The main goal of this paper is to prove the following result:
Theorem 1. Let \(n \in \mathbf{N}, n\ge2\), then we have \[f_{\frak{s},\frak{o}}(n) = \begin{cases} \lceil \log_2(n) \rceil + 3 & \text{if } n = 2^m-1, \\ \lceil \log_2(n) \rceil + 2 & \text{otherwise.} \end{cases}\]
An intriguing feature of the problem is that the sequence is not monotone.
The paper is organized as follows. We start by considering the conditions (\(\frak{s}\)) in Section 2 and (\(\frak{o}\)) in Section 3 separately. The combined problem of finding an optimal playing schedule satisfying both conditions (\(\frak{s}\)) and (\(\frak{o}\)) is treated in Section 4. In particular, this section will contain the proof of the main Theorem 1. But first, we fix some notation and notions that we will use in the sequel.
We write \(S_{k\times m}\) to denote an array of \(k\) rows and \(m\) columns with entries \(s_{i,j}\in\{0,1\}\) in row \(i\) and column \(j\). If the dimension of the array is clear from the context, we just write \(S\). The columns of \(S_{k\times m}\) are denoted by \(C_j\), \(j=1,\ldots,m\). Two columns are called complementary if their componentwise sum is 1 modulo 2. We write \(\overline{C}\) for the complementary column of \(C\).
An array \(S_{k\times 2n}\) is called a playing schedule of length \(k\) for \(2n\) players. If each row of \(S\) contains \(n\) \(0\)’s and \(n\) \(1\)’s, it is called a valid playing schedule.
The interpretation is as follows: the entry \(s_{i,j}\in\{0,1\}\) means that in game \(i\) player \(j\) plays in team \(s_{i,j}\). Observe that \(S\) satisfies (\(\frak{s}\)) if it does not contain complementary columns, and \(S\) satisfies (\(\frak{o}\)) if all columns are different. A valid playing schedule \(S\) is called admissible if it satisfies both conditions, (\(\frak{s}\)) and (\(\frak{o}\)).
The concept of a playing schedule satisfying the condition (\(\frak{o}\)) is related to the notion of separating systems which goes back to Rényi [11] (see also Katona [12]).
Definition 1. A separating system on a finite set \(M\) is a collection \(\{A_1,A_2,\dots,A_k\}\) of subsets of \(M\) such that for every pair of distinct elements \(x,y \in M\), there exists \(i \in \{ 1,2,\dots,k\}\) with either \(x \in A_i, y \notin A_i\) or \(x \notin A_i , y \in A_i\). Moreover, a covering separating system is a separating system such that \(M\) is the union of the sets \(A_i\). More specifically, we call a covering separating system an \(\boldsymbol{(n,k)}\)-covering separating system if \(|M| = n\) and for all \(i\) we have \(|A_i|=k\).
We can interpret a playing schedule \(S\) of length \(k\) for \(2n\) players as a set \(M = \{1,2, \dots, 2n \}\) and a collection \(\{A_1,A_2,\dots,A_k\}\) of subsets of \(M\) with \(|A_i|=n\), such that \(j \in A_i\) if and only if \(s_{i,j} = 1\). Then we clearly have that \(S\) satisfies the condition (\(\frak{o}\)) if and only if \(\{A_1,A_2,\dots,A_k\}\) is a separating system on \(M\).
Definition 2. Two columns \(C_i,C_j\) of a playing schedule \(S_{k,2n}\) are called equivalent, written \(C_i\sim C_j\), if \(C_i=C_j\) or \(C_i=\overline{C_j}\). The cardinality of the equivalence class of \(C_i\) in \(S_{k,2n}\) is called the characteristic of the column \(C_i\).
Example 1. Let \[S = \begin{pmatrix} 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ \end{pmatrix}\] be a playing schedule, then the columns \(C_1,C_3\) and \(C_4\) are equivalent, and hence the characteristic of these columns is 3, while the characteristic of \(C_3\) is 1.
Definition 3. Let \(S_{k\times 2n}\) and \(E_{t\times 2n}\) be two playing schedules. Then we can build a new playing schedule \(S'=S\oplus E\) with \(k+t\) rows by putting the array \(S\) on top of \(E\) (see Example 2). \(E\) is called an extension of \(S\) of length \(t\). If all columns of \(S'\) have characteristic \(1\), then \(E\) is called sufficient. If \(E\) is valid and sufficient, then it is called an admissible extension.
Example 2. Let \[S = \,\begin{pmatrix} 0& 0& 1& 1\\ 0& 0& 1& 1\\ \end{pmatrix}\ .\] Then\[E = \left(\ \,\begin{matrix} 1& 0& 0& 1\\ 0& 1& 0& 1\\ \end{matrix}\ \,\right)\] is an admissible extension of \(S\) of length \(2\), and \[S' = S \oplus E = \left(\ \,\begin{matrix} 0& 0& 1& 1\\ 0& 0& 1& 1\\ 1& 0& 0& 1\\ 0& 1& 0& 1\\ \end{matrix}\ \,\right).\] The playing schedule \(S'\) is valid and sufficient and hence admissible.
In this section we neglect condition (\(\frak{o}\)) and consider only condition (\(\frak{s}\)). We will denote by \(f_{\frak{s}}(n)\) the minimal number of rounds needed to satisfy condition (\(\frak{s}\)). We find:
Theorem 2. For \(n\ge 2\), \(f_{\frak{s}}(n)=\begin{cases}3&\text{if $n$ is even,}\\4&\text{if $n$ is odd.}\end{cases}\)
Proof. If \(n\) is even, then
\[ S=\left( \begin{array}{cccc|cccc|cccc|cccc} 0 & 0 & … & 0 & 0 & 0 & … & 0 & 1 & 1 & … & 1 & 1 & 1 & … & 1\\ 0 & 0 & … & 0 & 1 & 1 & … & 1 & 0 & 0 & … & 0 & 1 & 1 & … & 1\\ 0 & 0 & … & 0 & 1 & 1 & … & 1 & 1 & 1 & … & 1 & 0 & 0 & … & 0 \end{array} \right) \]is a playing schedule satisfying condition (\(\frak{s}\)). Here each of the four subarrays in \(S\) contains \(\frac n2\) columns.
If \(n\) is odd, a possible playing schedule has the form
$$ S=\left( \begin{array}{c|cccc|cccc|cccc|cccc|c} 0 & 0 & 0 & \ldots & 0 & 0 & 0 & \ldots & 0 & 1 & 1 & \ldots & 1 & 1 & 1 & \ldots & 1 & 1\\ 0 & 0 & 0 & \ldots & 0 & 1 & 1 & \ldots & 1 & 0 & 0 & \ldots & 0 & 1 & 1 & \ldots & 1 & 1 \\ 0 & 0 & 0 & \ldots & 0 & 1 & 1 & \ldots & 1 & 1 & 1 & \ldots & 1 & 0 & 0 & \ldots & 0 & 1 \\ 0 & 0 & 0 & \ldots & 0 & * & * & \ldots & * & * & * & \ldots & * & * & * & \ldots &* & 0 \end{array} \right) $$where each of the four big subarrays contained in the middle of \(S\) consists of \(\frac{n-1}2\) columns. Each entry marked with \(*\) can be independently replaced by either \(0\) or \(1\) as long as the condition is satisfied that the last row of \(S\) contains the same number of \(0\)’s and \(1\)’s.
It remains to show that no shorter playing schedules exists. To see this, notice first that columns (and rows) of a playing schedule \(S\) which satisfies condition (\(\frak{s}\)) can be permuted and the result is still a playing schedule which satisfies condition (\(\frak{s}\)). In particular we may assume that the first row of \(S\) has the form
$$ \left( \begin{array}{cccc|cccc} 0&0&\ldots& 0 & 1&1& \ldots 1 \end{array} \right). $$We now state condition (\(\frak{s}\)) in the following form: for each pair \((k,l)\) with \(1\le k<l\le 2n\) there is a \(j\) such that \(s_{j,k}=s_{j,l}\). These are \(\binom{2n}2\) conditions. The first row saturates \(2\binom n2\) such conditions. So the remaining rows must satisfy the remaining \(\binom{2n}2-2\binom n2 = n^2\) conditions. Suppose the second row consists of \(n_1\) zeros and \(n-n_1\) ones in the first \(n\) columns, and hence \(n-n_1\) zeros and \(n_1\) ones in the last \(n\) columns. This gives additional \(2n_1(n-n_1)<n^2\) conditions to the conditions which are already satisfied by the first row. This implies that \(S\) cannot satisfy condition (\(\frak{s}\)) if it has only two rows.
Similarly for the third row of \(S\): It consists of \(n_2\) zeros and \(n-n_2\) ones in the first \(n\) columns, and hence \(n-n_2\) zeros and \(n_2\) ones in the last \(n\) columns. This provides at most \(2n_2(n-n_2)\) additional conditions to the conditions we already have. Observe that \[\max_{0\le n_1,n_2\le n}2n_1(n-n_1)+2n_2(n-n_2)=\begin{cases}n^2&\text{if $n$ is even}\\ n^2-1&\text{if $n$ is odd.}\end{cases}\] Hence, if \(n\) is odd, \(S\) cannot satisfy condition (\(\frak{s}\)) if it has only three rows. This completes the proof. ◻
In this section we neglect condition (\(\frak{s}\)) and consider only condition (\(\frak{o}\)). We denote by \(f_{\frak{o}}(n)\) the minimal number of rounds required to satisfy condition (\(\frak{o}\)). In the language of separating systems we need a separating system \(A_1,A_2,\ldots,A_m\) with minimal \(m\) on the set \(\{1,2,\ldots,2n\}\) such that every set \(A_i\) hat cardinality \(n\). We find the following.
Theorem 3. \(f_{\frak{o}}(n) = \lceil \log_2(n) \rceil + 1.\)
Proof. First we show that \(f_{\frak{o}}(n) \leq \lceil \log_2(n) \rceil + 1\). For this it is enough to construct a playing schedule of length \(m \lceil \log_2(n) \rceil + 1 = \lceil \log_2(2n) \rceil\) for \(2n\) players. Since there exist more than \(2n\) different columns (note that \(2n \leq 2^{\lceil \log_2(2n) \rceil}\)) of length \(m\) with entries in \(\{ 0,1 \}\), we can find \(n\) different columns having \(0\) as last entry. Then we define \(S\) to be the array which contains all these columns and their complements. Since all columns in \(S\) are different, (\(\frak{o}\)) is satisfied. Moreover \(S\) is valid by construction (see Example 3).
On the other hand, the minimal separating system of a set of \(2n\) elements has at least cardinality \(\lceil \log_2 n \rceil+1\) (see [11]). Indeed, to show the inequality \(f_{\frak{o}}(n) \leq \lceil \log_2(n) \rceil + 1\) we argue as follows: A playing schedule with length strictly smaller than \(\lceil \log_2(n) \rceil + 1\) for \(2n\) players contains at least one pair of identical columns by the pigeonhole principle. Hence, no such playing schedule satisfies (\(\frak{o}\)). ◻
Example 3. We illustrate the construction of an optimal playing schedule \(S\) for \(n=11\). The gray subarray is our choice of columns with length \(5\) (the columns correspond to the binary representation of the numbers \(0,1,2,\ldots,10\)) where the last entry is \(0\) and the white subarray is the complement of the grey one. Then \(S\) is a playing schedule of minimal length satisfying \((\frak o)\).
To find an optimal playing schedule for \(2n\) players that satisfies both conditions \((\frak s)\) and \((\frak o)\) is considerably harder than for just one of the two conditions. We start with lower and upper bounds for the minimal length \(f_{\frak{s},\frak{o}}(n)\) for particular values of \(n\). These bounds are improved and extended gradually, and finally lead to a proof of the main Theorem 1.
We clearly have \(\max\{f_{\frak{s}}(n),f_{\frak{o}}(n)\} \leq f_{\frak{s},\frak{o}}(n) \leq f_{\frak{s}}(n) + f_{\frak{o}}(n)\) and so we get that \[\max\left\{4 – \chi_{\text{even}}(n),\lceil\log_2(n) \rceil + 1 \right\} \leq f_{\frak{s},\frak{o}}(n) \leq \lceil\log_2(n) \rceil + 5 -\chi_{\text{even}}(n)\] for all \(n \in \mathbf{N}, n\ge 2\). Here, \(\chi_{\text{even}}(n)=1\) if \(n\) is even, and \(0\) if \(n\) is odd. In this section we would like to improve these bounds.
By using covering separating systems we can estimate \(k := f_{\frak{s},\frak{o}}(n)\) from below. Assume that we have a minimal valid playing schedule \(S\) of length \(k\) for \(2n\) players. Without loss of generality, we can assume that player \(2n\) is always in the team \(1\), i.e., the last column of \(S\) consists of \(1\)’s, and the first \(n\) players play against the second \(n\) players in the first game. Hence, the first row of \(S\) consists of \(n\) \(0\)’s followed by \(n\) \(1\)’s. Consider now the collection \(\{ A_1, \cdots, A_k \}\) of subsets of \(\{1,2 \dots, 2n\}\) where \(j \in A_i\) if and only if \(s_{i,j} = 1\). Then \(\{A_1, \cdots, A_k\}\) forms an \((2n,n)\)-covering separating system because otherwise \(S\) would violate the conditions (\(\frak{s}\)) and/or (\(\frak{o}\)). Hence, by Phanalasy et al. [13, Lemma 5] we get that \(k \geq \lfloor \log_2(n) \rfloor + 2\). If \(n = 2^m\) for \(m \in \mathbb{N} \setminus \{ 0 \}\), then this estimate coincides with the next result. In every other case we will find a better lower bound for \(k\).
Proposition 1. For all \(n \in \mathbf{N}\setminus \{ 0,1 \}\) we have \(f_{\frak{s},\frak{o}}(n) \geq \lceil \log_2(n) \rceil + 2.\)
Proof. Let \(k:= f_{\frak{s},\frak{o}}(n)\). Then there exists a playing schedule \(S\) with \(k\) rows and \(2n\) columns. Since \(S\) is admissible, the columns of \(S\) are all different, and no two columns of \(S\) are complementary to each other. There exist \(2^k\) different columns of length \(k\). However, only \(2^{k-1}\) of these are not complementary and this number must be larger than or equal to the number of columns in \(S\). Hence, we get \(2^{k-1} \geq 2n\) which proves the proposition. ◻
Example 4. Consider a playing schedule \(S\) for \(2n= 4\) players. By the inequality \(2^{k-1} \geq 2n\) in the proof of Proposition 1 where \(k:= f_{\frak{s},\frak{o}}(n)\), we have that \(k \geq 3\). In fact, we can find the following valid and admissible playing schedule for \(k = 3\), and hence \(f_{\frak{s},\frak{o}}(2)=3\):
\[S =\begin{pmatrix} 0& 0& 1 & 1 \\ 0& 1& 0 & 1 \\ 0& 1& 1 & 0 \\ \end{pmatrix}.\]
In this section we determine \(f_{\frak{s},\frak{o}}(n)\) if \(n\) is a power of \(2\). Moreover, we find an upper bound for \(f_{\frak{s},\frak{o}}(n)\).
Theorem 4. For \(m \in \mathbb{N} \setminus \{ 0 \}\) we have \(f_{\frak{s},\frak{o}}(2^m) = m+2\).
To prove this theorem, we need the following lemma:
Lemma 1. For \(m \geq 2\) we have \(f_{\frak{s},\frak{o}}(2^m) \leq f_{\frak{s},\frak{o}}(2^{m-1}) + 1\).
Proof. We show that a valid playing schedule \(S\) of length \(f_{\frak{s},\frak{o}}(2^{m-1})\) for \(2^m\) players can be extended to a valid playing schedule \(S^{+}\) of length \(f_{\frak{s},\frak{o}}(2^{m-1}) + 1\) for \(2^{m+1}\) players. To do so, we define the columns of \(S^+\) by \[\begin{aligned} C_i^{+} &:= \ C_i \oplus 0 \ \text{for} \ 1 \leq i \leq 2^{m} \\ C_i^{+} &:= \ C_{i-2^m} \oplus 1 \ \text{for} \ 2^{m} < i \leq 2^{m+1}. \end{aligned}\] Observe that all columns of \(S^{+}\) are different from each other and not complementary to another column in \(S^{+}\). Hence, \(S^{+}\) defines a valid and admissible playing schedule for \(2^{m+1}\) players. ◻
With this preparation we are ready for the proof of Theorem 4.
Proof of Theorem 4. For \(m=1\) the statement is true by Example 4. Now we assume that this is the case for an arbitrary \(m\) and show it for \(m+1\). By using Proposition 1, Lemma 1 and the induction hypothesis \(f_{\frak{s},\frak{o}}(2^m) = m + 2\) we get the desired result \[m + 3 = \lceil \log_2(2^{m+1}) \rceil + 2 \leq f_{\frak{s},\frak{o}}(2^{m+1}) \leq f_{\frak{s},\frak{o}}(2^{m}) + 1 = m+3.\] ◻
Example 5. Let \(S\) be a valid and admissible playing schedule for \(4\) players of length \(3\), as in Example 4:
\[ S =\left(\ \,\begin{matrix} 0& 0& 1 & 1 \\ 0& 1& 0 & 1 \\ 0& 1& 1 & 0 \\ \end{matrix}\ \,\right).\]Following the construction in the proof of Lemma 1, we obtain an optimal playing schedule
\[ S^{+} =\left(\ \, \begin{matrix} 0& 0& 1 & 1 \\ 0& 1& 0 & 1 \\ 0& 1& 1 & 0 \\ 0& 0& 0 & 0 \\ \end{matrix}\ \ \ \begin{matrix} 0& 0& 1 & 1 \\ 0& 1& 0 & 1 \\ 0& 1& 1 & 0 \\ 1& 1& 1 & 1 \\ \end{matrix} \ \,\right) \]for \(8\) players.
We will now introduce a helpful tool which we use to prove the upper bound of \(f_{\frak{s},\frak{o}}(n)\).
Definition 4. For a column \(C\) of a playing schedule, we call the array \(T(C)\) consisting of the three columns \(C,C,\overline{C}\) a triplet of \(C\).
Proposition 2. For all \(n \in \mathbf{N}\setminus \{ 0,1 \}\) we have \(f_{\frak s,\frak o}(n) \leq \lceil \log_2(n) \rceil + 3\).
Proof. The case \(n=2\) is verified by Example 4. Therefore let \(n \in \mathbf{N}\setminus \{ 0,1,2 \}\), and \(m \in \mathbf{N}\setminus \{ 0 \}\) the unique value such that \(2^m < n \leq 2^{m+1}\). Let \(S\) be a valid and admissible playing schedule of length \(m+2\) for \(2^{m+1}\) players (see Theorem 4). We construct a playing schedule \(S^{+}\) of length \(\lceil \log_2(n) \rceil + 3 = m + 4\) for \(2n\) players as follows.
For the columns \(C_i\) of \(S\) with \(1 \leq i \leq n-2^m\) let \(T(C_i)^{+} = T(C_i) \oplus E_i\), where
Let \(C_{i}^{+} = C_{i} \oplus (_{*}^{*})\) be an extension of the remaining columns \(C_{i}\) of length \(2\) for \(n-2^m+1 \leq i \leq 2^{m+1}\). Then we define \[S^{+} = (T(C_1)^{+}, T(C_2)^{+}, \dots, T(C_{n-2^m})^{+}, C_{n-2^{m}+1}^{+}, \dots, C_{2^{m+1}}^{+}).\] Observe that \(S^{+}\) is admissible because \(S\) was admissible. It remains to show that \(S^{+}\) is valid. The first \(m+2\) rows contain the same number of \(0\)’s and \(1\)’s by construction. Observe, that we used all columns of \(S\) and added pairs of columns and their complements. For the last two rows we choose the \(*\)’s in the \(C_{i}^{+}\) as follows. The numbers of triplets in \(S^+\) and the number of \(C_i^+\) are either both even or both odd. In the even case the extensions in the \(C_i^+\) must be chosen such the last two rows of the \(C_i^{+}\) contain the same number of \(0\)’s and \(1\)’s. In the odd case, there must be one more \(0\) than \(1\)’s in the second last row of the \(C_{i}^{+}\), and three \(1\)’s more than \(0\)’s in the last row. The result is a valid and admissible playing schedule \(S^{+}\) of length \(m+4\) for \(2n\) players. ◻
Example 6. Consider the case \(n = 3\). We start with a valid and admissible playing schedule \(S\) for \(4\) players of length \(3\):
We have
\[ S =\left(\ \,\begin{matrix} 0& 0& 1 & 1 \\ 0& 1& 0 & 1 \\ 0& 1& 1 & 0 \\ \end{matrix} \ \,\right).\] We have \[ T(C_1) = \left(\ \,\begin{matrix} 0& 0& 1 \\ 0& 0& 1 \\ 0& 0& 1 \\ \end{matrix}\ \,\right) \text{ and} T(C_1)^{+} =\left(\ \,\begin{matrix} 0& 0& 1 \\ 0& 0& 1 \\ 0& 0& 1 \\ 1& 0& 1 \\ 0& 0& 0 \\ \end{matrix}\ \,\right).\]The construction in the proof of Proposition 2 yields \(S^{+} = (T(C_1)^{+},C_2^{+},C_3^{+},C_4^{+})\), where \(C_2^{+},C_3^{+},C_4^{+}\) are chosen such that \(S^{+}\) is valid. A possibility is
\[ S^{+} = \left(\ \,\begin{matrix} 0& 0& 1 & 0& 1& 1\\ 0& 0& 1 & 1& 0& 1\\ 0& 0& 1 & 1& 1& 0\\ 1& 0& 1 & 0& 0& 1\\ 0& 0& 0 & 1& 1& 1\\ \end{matrix}\ \,\right). \]With Proposition 1 and Proposition 2 we conclude:
Corollary 1. For all \(n \in \mathbf{N}\setminus \{ 0,1 \}\) we have \[\lceil \log_2(n) \rceil + 2 \leq f_{\frak{s},\frak{o}}(n) \leq \lceil \log_2(n) \rceil + 3.\]
So far we know that for each \(n \in \mathbf{N}\setminus \{ 0,1 \}\) there are only two possible values for \(f_{\frak{s},\frak{o}}(n)\). In this section determine the exact value of \(f_{\frak{s},\frak{o}}(n)\) for even \(n\).
Theorem 5. If \(n \in \mathbf{N}\setminus \{ 0,1 \}\) is even, then we have \[f_{\frak{s},\frak{o}}(n) = \lceil \log_2(n) \rceil + 2.\]
Proof. We start with an admissible playing schedule for \(4\) players. For example, we can consider \[S := \left( \begin{array}{rrrr} 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right)\] with columns \(C_1,\ldots, C_4\). Since \(n = 2m\), an admissible and valid playing schedule for \(n\) consists of \(4m\) players. We define the arrays \[S_i := (\underbrace{C_i,C_i, \dots ,C_i}_{m \ \text{times}})\] with \(m\) columns for \(i = 1,\ldots,4\). The idea is now to find a playing schedule for \(2m\) players of length \(\lceil \log_2(n) \rceil + 2 = \lceil \log_2(m) \rceil + 3\), of the form \[S^{+} = \left( \begin{array}{rrrr} S_1 & S_2 & S_3 & S_4 \\ E & E & \overline{E} & \overline{E} \\ \end{array} \right).\] Here \(E\) consists of \(m\) different column vectors of length \({\lceil \log_2(m) \rceil}\). Observe that two columns from different arrays \(S_i\) are neither the same nor the complement of each other. Hence, \(S^{+}\) is a valid and admissible playing schedule for \(2n\) players. This implies \(f_{\frak{s},\frak{o}}(n) \leq \lceil \log_2(n) \rceil + 2\) and the result follows by Corollary 1. ◻
To show \(f_{\frak{s},\frak{o}}(n) \leq \lceil \log_2(n) \rceil + 2\) if \(n\) is even, we can alternatively define a playing schedule in the following way: Choose \(n\) different pairs of columns of length \(\lceil \log_2(n) \rceil + 1\) such that the columns in each pair are complementary. Then define \(S\) as the array containing all columns of these pairs such that the columns of each pair belong either to the first \(n\) or to the last \(n\) columns of \(S\) (note that this only works if \(n\) is even). If we extend \(S\) by the row \[E= \left( \begin{array}{cccc|cccc} 0&0&\ldots& 0 & 1&1& \ldots 1 \end{array} \right),\] containing \(n\) \(0\)’s followed by \(n\) \(1\)’s, then \(S^{+}=S\oplus E\) is valid and there are no columns in \(S^{+}\) which are equal or the complement of each other. Hence, \(S^{+}\) satisfies (\(\frak{o}\)) and (\(\frak{s}\)) and its length is \(\lceil \log_2(n) \rceil + 2\) which shows that \(f_{\frak{s},\frak{o}}(n) \leq \lceil \log_2(n) \rceil + 2\).
The case \(n\) odd is more delicate than the case \(n\) even. We start with some general considerations. In the proof of Proposition 2 we had to extend the triplets by an extension of length \(2\). We now ask, by how many rows must a given playing schedule be extended in order to obtain an admissible playing schedule. For this, the characteristic of the columns (see Definitions 2 and 3) plays the decisive role. More concretely, we find a lower bound for the length of an admissible extension as a function of its largest characteristic.
Theorem 6. Let \(S\) be a playing schedule, and \(k\) be the maximal characteristic of the columns in \(S\). Then an admissible extension of \(S\) has at least length \(\lceil \log_2(k) \rceil\).
Proof. Let \(C_u\) be a column of \(S\) with maximal characteristic \(k\), and \(U\) the array built from the columns in the equivalence class of \(C_u\). We show that the minimal length \(t\) of an admissible extension \(E\) of \(U\) is at least \(\lceil \log_2(k) \rceil\).
Observe first that the maximal characteristic of the columns of \(E\) is \(\le 2\). To see this, assume that this is not the case. Then there are three equivalent columns in \(E\), say \[E_{j'} \sim E_{j''} \sim E_{j'''}\] and we have \[C_{j'}' = C_{j'} \oplus E_{j'},\quad C_{j''}' = C_{j''} \oplus E_{j''} ,\quad C_{j'''}' = C_{j'''} \oplus E_{j'''},\] where \(C_{j'} \sim C_{j''} \sim C_{j'''}\) by assumption. Since \(E\) is supposed to be sufficient, any two of the vectors \(C_{j'}', C_{j''}', C_{j'''}'\) are pairwise distinct and pairwise nonequivalent. At least two of the vectors \(C_{j'},C_{j''},C_{j'''}\) are equal, say \(C_{j'}=C_{j''}\). It follows that \(E_{j'}=\overline{E_{j''}}\). But then, in the case \(C_{j'''}=C_{j'}\) as well as in the case \(C_{j'''}=\overline{C_{j'}}\), \(E_{j'''}\) can neither be equal to \(E_{j'}\) nor to \(E_{j''}\). So, we have a contradiction.
We know now that the characteristic of the columns in \(E\) can be at most \(2\). On the other hand if \(E\) is an extension of length \(t\), then we find at most \(2^{t-1}\) different equivalence classes among the columns of \(E\). Hence, the number of columns of \(E\) must be bounded by \(k\) because \[2^{t-1} \cdot 2 \geq k\] and this completes the proof. ◻
Remark 1. Note that the last inequality becomes an equality if there are exactly \(2^{t-1}\) equivalence classes in the columns of \(E\), and each equivalence class consists of two columns. Also note that the number of equivalence classes of the columns of \(E\) must be at least \(\tfrac{k}{2}\).
Example 7. Let
The maximal characteristic is \(k= 4\), and hence the minimal length of a sufficient extension \(E\) of \(U\) is \(2\). For example, we can choose
and get
In the following we will analyse the structure of the equivalence classes more closely. We only need to discuss the case when \(M_1\) and \(M_2\) have the same odd cardinality as we see later.
Theorem 7. Let \(S\) be a playing schedule, and \([C_u]\) be the equivalence class of a column of \(S\) with characteristic \(k > 1\). Assume that the sets \[M_1 := \{ C_j \in [C_u] : C_j = C_u \} \text{ and }M_2 := \{ C_j \in [C_u] : C_j = \overline{C_u} \}\] have odd cardinality \(q := \vert M_1 \vert = \vert M_2 \vert > 1\). Let \(U\) be the array built from the columns in \([C_u]\). Then the minimal length \(t\) of an admissible extension \(E\) of \(U\) satisfies \(t \geq \lceil \log_2(q + 2) \rceil + 1\).
In order to prove Theorem 7 we will show that the columns of \(E\) must contain at least \(q + 2\) equivalence classes. This is done in the next two lemmas.
Lemma 2. For an admissible extension \(E\) of \(U\), the columns of \(E\) must contain more than \(q\) equivalence classes.
Proof. We have seen in the proof of Theorem 6 that each equivalence class of columns of \(E\) contains at most 2 elements. Hence, the columns of \(E\) contain at least \(q\) equivalence classes. Assume now that here are exactly \(q\) equivalence classes and work towards a contradiction. In this situation every equivalence class contains two elements. These two elements are either equal or the complement of each other. Hence, we can choose representatives \(E_1,E_2, \dots, E_q\) of each equivalence class, and a natural number \(0 \leq c \leq q\) such that, after reordering the columns if necessary, we have \[E = (E_1,E_1,E_2,E_2 \dots, E_c,E_c, E_{c+1}, \overline{E_{c+1}}, \dots, E_q, \overline{E_q}).\] Since the columns of \(U\) all belong to the same equivalence class, and \(U'\) is admissible by assumption, there exists a column \(C\) in \(U\) such that \[U = (\underbrace{C,\overline{C}, \dots, C, \overline{C}}_{2c \ \text{columns}},\underbrace{*, \dots, *}_{2(q-c) \ \text{columns}}),\] where two consecutive \(*\) are either equal to \(C\) or \(\overline{C}\). However, the number of consecutive pairs of \(C\) and \(\overline{C}\) in \(U\) must be the same. Hence, the number of \(*\) in \(U\) must be divisible by \(4\) and so \(q-c\) is even and \(c\) is odd.
Moreover, since \(E\) is valid, we have that \(E' := (E_1,E_1,E_2,E_2 \dots, E_c,E_c)\) must also be valid and hence \(E'' := (E_1,E_2 \dots, E_c)\) is also valid. However, \(E''\) cannot be valid because its number of columns is \(c\) and \(c\) is odd. Thus, we get a contradiction. ◻
Lemma 3. For an admissible extension \(E\) of \(U\), the columns of \(E\) must contain more than \(q+1\) equivalence classes.
Proof. By Lemma 2 we already know that the columns of \(E\) contain at least \(q+1\) equivalence classes. To obtain a contradiction, assume that they contain exactly \(q+1\) equivalence classes. Then there are exactly \(q-1\) equivalence classes with \(2\) elements, and \(2\) equivalence classes with \(1\) element. Hence, we can assume that there exists a natural number \(0 \leq c \leq q-1\) such that \[E = (E_1,E_1,E_2,E_2, \dots, E_c,E_c, E_{c+1}, \overline{E_{c+1}}, \dots, E_{q-1}, \overline{E_{q-1}}, E_q,E_{q+1})\] for a choice of representatives \(E_1,E_2, \dots, E_{q+1}\) of all equivalence classes. As in Lemma 2, we find a column \(C\) in \(U\) such that \[U = (\underbrace{C,\overline{C}, \dots, C, \overline{C}}_{2c \ \text{columns}},\underbrace{*, \dots, *}_{2(q-c) \ \text{columns}}).\] Define now \[E' := (E_1,E_1,E_2,E_2, \dots, E_c,E_c, E_{c+1}, \overline{E_{c+1}}, \dots, E_{q-1}, \overline{E_{q-1}}).\] Since \(E\) is an admissible extension of \(U\), \(E'\) is not valid because otherwise \((E_q, E_{q+1})\) would also be valid and so \(E_q\) and \(E_{q+1}\) would be in the same equivalence class which is not the case. Thus, \[E'' := (E_1,E_2 \dots, E_c)\] cannot be valid. We now consider separately the cases, \(c\) even and \(c\) odd.
Let \(c\) be even. Since \(E''\) is not valid, there exists a row such that the difference of \(0\)’s and \(1\)’s in this row is at least \(2\). Hence, there is a row in \(E'\) such that the difference between the \(0\)’s and \(1\)’s is at least \(4\). Adding the missing two columns with characteristic \(1\) cannot make this playing schedule valid. Therefore we have a contradiction.
Let \(c\) be odd. Then the difference of \(0\)’s and \(1\)’s in each row of \(E''\) must be at least \(1\), and the difference of \(0\)’s and \(1\)’s in each row of \(E'\) is at least \(2\). Thus, adding two columns to \(E'\) to make it valid means that the two added columns \(E_q\) and \(E_{q+1}\) must be equal and this is a contradiction because they do not belong to the same equivalence class by assumption. ◻
Theorem 7 follows now from the lemma above.
Proof of Theorem 7. We showed that the columns of \(E\) contain at least \(q+2\) different equivalence classes. Then the result follows from the inequality \[2^{t-1} \geq q + 2 .\] ◻
Remark 2. For \(q = 1\) it is not possible to find an admissible extension. However, we will now show that for \(q>1\) we can construct an admissible extension with \(q + 2\) equivalence classes. This will be the last building block we need to prove Theorem 1.
Proposition 3. Let \(S\) be a playing schedule, and \([C_u]\) be the equivalence class of a column of \(S\) with characteristic \(k > 1\). Assume that the sets \[M_1 := \{ C_j \in [C_u] : C_j = C_u \} \text{ and}M_2 := \{ C_j \in [C_u] : C_j = \overline{C_u} \},\] have odd cardinality \(q := \vert M_1 \vert = \vert M_2 \vert > 1\). Let \(U\) be the array built from the columns in \([C_u]\). Then the minimal length \(t\) of an admissible extension \(E\) of \(U\) is \(t = \lceil \log_2(q + 2) \rceil + 1\).
Proof. By Lemma 3 it remains to show that an admissible extension \(E\) of \(U\) exists such that the columns of \(E\) contain exactly \(q + 2\) equivalence classes. Without loss of generality (by renumbering players), we can assume that \(U\) has the form \[U = (\underbrace{C, \dots, C}_{q \ \text{times}},\underbrace{\overline{C}, \dots, \overline{C}}_{q \ \text{times}}).\] First we consider the case \(q = 3\). Define \[E_{*} = (E_1, E_2, E_3, E_4, E_5, \overline{E_5}) := \left( \begin{array}{rrrrrr} 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ \end{array} \right),\] and note that \(E_*\) contains \(q+2 = 5\) different equivalence classes. It is easy to see that \(E_3\) is an admissible extension of \(U\) with length \(\lceil \log_2(q + 2) \rceil + 1 = 4\).
Now we assume that \(q > 3\). Let \(E_{*}\) be as above. If \(q = 5\), then set \(E_{*}^{+} = E_{*}\). Otherwise extend \(E_{*}\) to \(E_{*}^{+}\) by adding \(\lceil \log_2(q + 2) \rceil -3\) occurrences of the row \((0 \, 0 \,1\,1\,0\,1)\). Note that \(E_{*}^{+}\) is valid and consists of \(\lceil \log_2(q + 2) \rceil + 1\) rows and \(6\) columns which belongs to \(5\) different equivalence classes. The set of 01-sequences of length \(\lceil \log_2(q + 2) \rceil + 1\) contains at least \(q + 2\) equivalence classes. Hence, from this set, we can choose more representatives \(D_i\) from different equivalence classes such that they are all not equivalent with the columns in \(E_{*}^{+}\). Now we can define the arrays \((E_\text{left}, E_\text{right}) := (D_1, D_2, \dots, D_{q-3})\) where both, \(E_{\text{left}}\) and \(E_{\text{right}}\), have the same dimension. Observe that \((E_\text{left},\overline{E_\text{left}})\) and \((E_\text{right},\overline{E_\text{right}})\) are valid playing schedules for \(q-3\) players. Then, the set \[E := (\underbrace{E_\text{left},\overline{E_\text{left}}}_{q-3 \ \text{columns}},\underbrace{E_3^{+}}_{6 \ \text{columns}},\underbrace{E_\text{right},\overline{E_\text{right}}}_{q-3 \ \text{columns}}) ,\] is an admissible extension of \(U\) satisfying all the necessary conditions. ◻
Theorem 1 follows now from Proposition 3.
Proof of Theorem 1. Because of Theorem 5, it remains to treat the case \(n\) odd. Consider a valid playing schedule \(S\) of length \(1\) for \(2n\) players. We would like to construct a minimal admissible and valid playing schedule \(S^{+}\) for the \(2n\) players which extends \(S\). The columns \(C_j\) of \(S\) have length 1, and all belong to the same equivalence class \([(0)]\). \[M_1 := \{ C_j : C_j = (0) \} \text{ and } M_2 := \{ C_j : C_j = (1) \},\] have both cardinality \(n\). Then we can apply Proposition 3 to find a minimal admissible and valid extension \(E\) of \(S\) of length \(\lceil \log_2(n + 2) \rceil + 1\) for \(2n\) players. The resulting playing schedule \(S^{+}\) has length \(\lceil \log_2(n + 2) \rceil + 2\). This finishes the proof. ◻
All authors declare that they have no conflicts of interest.