},(\pi _{2})^{k},...,(\pi _{i-1})^{k},(\pi
_{i+1})^{k},...,(\pi _{p})^{k}
\end{eqnarray*}%
is terminal as well. This holds for every $1\leq i\leq p$ and
$k\geq \sum^{n}_{i=1}|\pi _{i}|$.
\end{cor}

This is a special case of Lemma~\ref{basic_lemma} where
$\sigma=\pi _{i+1}\circ \ldots \pi _{n}\circ \pi _{1}\ldots \circ
\pi _{i-1}$.


\subsection{The MC($n,2n-1$) upper bound}
\label{app:upperbound}



The proof we present shows somewhat more than
Theorem~\ref{thm:mainfull} says. A useful observation is that the scheduler
can ``trade'' a player $P$ for a chair $c$. Namely, he can keep
$P$ constantly on chair $c$ and be able, in return to move any
other player past $c$-chairs. In other words, this effectively
means the elimination of chair $c$ from all other words. This
suggests the following definition: If $\pi$ is a word over
alphabet $C$ and $B\subseteq C$, we denote by $\pi (B)$ the word
obtained from $\pi$ by deleting from it the letters from
$C\setminus B$.

Our construction is recursive. An inductive step should add one
player (i.e., a word) and two chairs. We carry out this step in
two installments: In the first we add a single chair and in the
second one we add a chair and a player. Both steps are accompanied
by conditions that counter the above-mentioned trading option.

\begin{proposition}
\label{main_prep} For every integer $n\geq 1$
\begin{itemize}
\item
There exist full words $s_{1},s_{2},...,s_{n}$ over the alphabet
$\{1,2,...,2n-1\}$ such that\\
$s_{1}(A),s_{2}(A),...,s_{p}(A)$ is a terminal collection for
every $p\leq n$, and every subset\\
$A \subseteq \{1,2,...,2n-1\}$ of cardinality $|A|=2p-1$.
\item
There exist full words $w_{1},w_{2},...,w_{n}$ over alphabet
$\{1,2...,2n\}$, such that\\
$w_{1}(B),w_{2}(B),...,w_{p}(B)$ is a terminal collection for
every $p\leq n$, and every subset\\
$B\subseteq \{1,2,...,2n\}$ of cardinality $|B|=2p-1$.
\end{itemize}
\end{proposition}


The words $s_{1},s_{2},...,s_{n}$ in Proposition~\ref{main_prep}
constitute a terminal collection and are hence an oblivious
$MC(n,2n-1)$ algorithm that proves the upper bound part of Theorem
\ref{thm:mainfull}. In the rest of this section we prove
Proposition~\ref{main_prep}.


\begin{proof}

As mentioned, the proof is by induction on $n$. For $n=1$ clearly
$s_{1}=11$ and $w_{1}=1122$ satisfy the conditions.

In the induction step we use the existence of
$s_{1},s_{2},...,s_{n}$ to construct $w_{1},w_{2},...,w_{n}$.
Likewise the construction of $s_{1},s_{2},...,s_{n+1}$ builds on
the existence of $w_{1},w_{2},...,w_{n}$.

\textbf{The transition from }$w_{1},w_{2},...,w_{n}$ \textbf{to }
$s_{1},s_{2},...,s_{n+1}$\textbf{:}

To simplify notations we assume that the words
$w_{1},w_{2},...,w_{n}$ in the alphabet $\{2,3,...,2n+1\}$ (rather
than $\{1,2,...,2n\}$) satisfy the proposition. Let $k:=\sum
|w_{i}|$ and define:

\begin{eqnarray*}
s_{1} &:&=1\otimes ((w_{1}\circ w_{2}\circ...\circ w_{n})^{2(2n+1)}) \\
\forall i=2,\ldots n+1~~~ s_{i} &:&=(w_{i-1})^{k(2n+1)}\circ 1
\end{eqnarray*}

Fix a subset $A\subseteq \{1,2,...,2n+1\}$ of cardinality
$|A|=2p-1$ with $p \le n+1$, and let us show that
$s_{1}(A),s_{2}(A),...,s_{p}(A)$ is a terminal collection. There
are two cases to consider:

We first assume ${1\notin A}$. This clearly implies that $p\leq n$
(or else $A=\{1,2,...,2n+1\}$ and in particular $1\in A$). In this
case the collection is:


\begin{eqnarray*}
s_{1}(A) &:&= ((w_{1}(A)\circ w_{2}(A)\circ...\circ w_{n}(A))^{2(2n+1)}) \\
\forall i=2,\ldots p~~~ s_{i}(A) &:&=(w_{i-1}(A))^{k(2n+1)}
\end{eqnarray*}


By the induction hypothesis, the collection
$w_{1}(A),w_{2}(A),...,w_{p-1}(A),w_{p}(A)$ is terminal. We apply
Corollary \ref{cor_2} and conclude that
\begin{eqnarray*}
(w_{1}(A)\circ w_{2}(A)\circ...\circ
w_{n}(A))^{2},(w_{1}(A))^{k},(w_{2}(A))^{k},...,(w_{p-1}(A))^{k}
\end{eqnarray*}
is terminal as well. But the $s_{i}$ are obtained by taking
$(2n+1)$-th powers of these words, so that
$s_{1}(A),s_{2}(A),...,s_{p}(A)$ is terminal as needed.


We now consider what happens when ${1\in A}$.

We define $F_{1}:=(w_{1}(A)\circ w_{2}(A)\circ...\circ
w_{n}(A))^{2}$ and for for $j>1$, let $F_{j}:=(w_{j-1}(A))^{k}$. We
refer to $F_{i}$ as the $i$-th block. In our construction each word
has $2n+1$ blocks, ignoring chair $1$.

At any moment throughout a schedule we denote by ${\cal O}_{1}$
the set of players in $\{P_{2},P_{3},...,P_{p}\}$ that currently
occupy chair $1$. We show that during a period in which the set
${\cal O}_1$ remains unchanged, no player can traverse a whole
block. The proof splits according to whether ${\cal O}_1$ is empty
or not.

Assume first that ${\cal O}_1\neq \emptyset$, and pick some $i>1$
for which $P_{i}$ occupies chair $1$ during the current period. As
long as ${\cal O}_1$ remains unchanged, $P_{i}$ stays on chair
$1$, so the words that the other players repeatedly traverse are
as follows: For $P_1$ it is

\[
w_{1}(A\backslash \{1\})\circ w_{2}(A\backslash
\{1\})\circ...\circ w_{n}(A\backslash \{1\})
\]

and for $P_j$ with $p \ge j \neq i \ge 2$ it is

\[
w_{j-1}(A\backslash \{1\})
\]


We now show that no player can traverse a whole block (as defined
above). Observe that the collection $\{w_{\nu}(A\backslash
\{1\})|\nu=1,\ldots,p-1\}$ (including, in particular the word
$w_{i-1}(A\backslash \{1\})$) is terminal. This follows from the
induction hypothesis, because $|A\backslash \{1\}|=2p-2$, and
because the property of being terminal is maintained under the
insertion of new chairs into words. Applying Corollary~\ref{cor_2}
to this terminal collection implies that this collection of blocks
is terminal as well.


We turn to consider the case ${\cal O}_1=\emptyset$. In this case
player $1$ cannot advance from a none-$