A Variant of the Round-Robin Scheduling Problem

Proof. If $n$ is even, then

is a playing schedule satisfying condition ($\mathfrak{s}$). Here each of the four subarrays in $S$ contains $\frac{n}{2}$ columns.

If $n$ is odd, a possible playing schedule has the form

where each of the four big subarrays contained in the middle of $S$ consists of $\frac{n-1}{2}$ columns. Each entry marked with $\ast$ 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 ($\mathfrak{s}$) can be permuted and the result is still a playing schedule which satisfies condition ($\mathfrak{s}$). In particular we may assume that the first row of $S$ has the form

We now state condition ($\mathfrak{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 $(\genfrac{}{}{0ex}{}{2n}{2})$ conditions. The first row saturates $2(\genfrac{}{}{0ex}{}{n}{2})$ such conditions. So the remaining rows must satisfy the remaining $(\genfrac{}{}{0ex}{}{2n}{2})-2(\genfrac{}{}{0ex}{}{n}{2})=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 ($\mathfrak{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 $$\underset{0\le n_1,n_2\le n}{max}2n_1(n-n_1)+2n_2(n-n_2)=\{\begin{array}{ll}{n}^2& \text{if }n\text{ is even}\\ n^2-1& \text{if }n\text{ is odd.}\end{array}$$ Hence, if $n$ is odd, $S$ cannot satisfy condition ($\mathfrak{s}$) if it has only three rows. This completes the proof. 

Proof. First we show that $f_{\mathfrak{o}}(n)\le \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\le 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, ($\mathfrak{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_{\mathfrak{o}}(n)\le \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 ($\mathfrak{o}$). 

Proof. Let $k:=f_{\mathfrak{s}\mathfrak{,}\mathfrak{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}\ge 2n$ which proves the proposition. 

Proof. We show that a valid playing schedule $S$ of length $f_{\mathfrak{s}\mathfrak{,}\mathfrak{o}}(2^{m-1})$ for $2^m$ players can be extended to a valid playing schedule $S^{+}$ of length $f_{\mathfrak{s}\mathfrak{,}\mathfrak{o}}(2^{m-1})+1$ for $2^{m+1}$ players. To do so, we define the columns of $S^{+}$ by $$\begin{array}{rl}{C}_i^{+}& :=C_i\oplus 0\text{for}1\le i\le 2^m\\ C_i^{+}& :=C_{i-2^m}\oplus 1\text{for}{2}^m<i\le 2^{m+1}.\end{array}$$ 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. 

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_{\mathfrak{s}\mathfrak{,}\mathfrak{o}}(2^m)=m+2$ we get the desired result $$m+3=\lceil {\log }_2(2^{m+1})\rceil +2\le f_{\mathfrak{s}\mathfrak{,}\mathfrak{o}}(2^{m+1})\le f_{\mathfrak{s}\mathfrak{,}\mathfrak{o}}(2^m)+1=m+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\le 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\le i\le n-2^m$ let $T(C_i{)}^{+}=T(C_i)\oplus E_i$, where

Let $C_i^{+}=C_i\oplus {(}_{\ast }^{\ast })$ be an extension of the remaining columns $C_i$ of length $2$ for $n-2^m+1\le i\le 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 $\ast$’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. 

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,\dots ,C_4$. Since $n=2m$, an admissible and valid playing schedule for $n$ consists of $4m$ players. We define the arrays $$S_i:=(\underset{m\text{times}}{\underbrace{C_i,C_i,\dots ,C_i}})$$ with $m$ columns for $i=1,\dots ,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_{\mathfrak{s}\mathfrak{,}\mathfrak{o}}(n)\le \lceil {\log }_2(n)\rceil +2$ and the result follows by Corollary 1. 

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^{\prime }}\sim E_{j^{″}}\sim E_{j^{‴}}$$ and we have $$C_{j^{\prime }}^{\prime }=C_{j^{\prime }}\oplus E_{j^{\prime }},C_{j^{″}}^{\prime }=C_{j^{″}}\oplus E_{j^{″}},C_{j^{‴}}^{\prime }=C_{j^{‴}}\oplus E_{j^{‴}},$$ where $C_{j^{\prime }}\sim C_{j^{″}}\sim C_{j^{‴}}$ by assumption. Since $E$ is supposed to be sufficient, any two of the vectors $C_{j^{\prime }}^{\prime },C_{j^{″}}^{\prime },C_{j^{‴}}^{\prime }$ are pairwise distinct and pairwise nonequivalent. At least two of the vectors $C_{j^{\prime }},C_{j^{″}},C_{j^{‴}}$ are equal, say $C_{j^{\prime }}=C_{j^{″}}$. It follows that $E_{j^{\prime }}=\overline{E_{j^{″}}}$. But then, in the case $C_{j^{‴}}=C_{j^{\prime }}$ as well as in the case $C_{j^{‴}}=\overline{C_{j^{\prime }}}$, $E_{j^{‴}}$ can neither be equal to $E_{j^{\prime }}$ 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\ge k$$ and this completes the proof. 

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\le c\le 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^{\prime }$ is admissible by assumption, there exists a column $C$ in $U$ such that $$U=(\underset{2c\text{columns}}{\underbrace{C,\overline{C},\dots ,C,\overline{C}}},\underset{2(q-c)\text{columns}}{\underbrace{\ast ,\dots ,\ast }}),$$ where two consecutive $\ast$ 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 $\ast$ 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^{\prime }:=(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. 

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\le c\le 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=(\underset{2c\text{columns}}{\underbrace{C,\overline{C},\dots ,C,\overline{C}}},\underset{2(q-c)\text{columns}}{\underbrace{\ast ,\dots ,\ast }}).$$ Define now $$E^{\prime }:=(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^{\prime }$ 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^{\prime }$ 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^{\prime }$ is at least $2$. Thus, adding two columns to $E^{\prime }$ 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. 

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}\ge q+2.$$ 

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=(\underset{q\text{times}}{\underbrace{C,\dots ,C}},\underset{q\text{times}}{\underbrace{\overline{C},\dots ,\overline{C}}}).$$ First we consider the case $q=3$. Define $$E_{\ast }=(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_{\ast }$ 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_{\ast }$ be as above. If $q=5$, then set $E_{\ast }^{+}=E_{\ast }$. Otherwise extend $E_{\ast }$ to $E_{\ast }^{+}$ by adding $\lceil {\log }_2(q+2)\rceil -3$ occurrences of the row $(001101)$. Note that $E_{\ast }^{+}$ 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_{\ast }^{+}$. 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:=(\underset{q-3\text{columns}}{\underbrace{E_{\text{left}},\overline{E_{\text{left}}}}},\underset{6\text{columns}}{\underbrace{E_3^{+}}},\underset{q-3\text{columns}}{\underbrace{E_{\text{right}},\overline{E_{\text{right}}}}}),$$ is an admissible extension of $U$ satisfying all the necessary conditions. 

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.