were made. That is, $y$ is a function of $x$, and does not depend on the specific order in which the algorithm performs the marking. This assertion can be proven easily by induction on $n$. As a consequence, we may choose the ordering of the $10$ pairs as we wish. We will use this fact in the proof of Theorem \[thm:main\].

The Bijection $\boldsymbol{{\psi}}$ {#sec:f}
-----------------------------------

We define the mapping ${\psi}$ as follows. Let $n \in {{\mathbb N}}$ be an even integer. For an input $x \in {\{0,1\}^{n}}$, let $C = \{ c_k, c_{k+1}, \ldots, c_{n-k}\}$ be the symmetric chain from the partition of De Bruijn [et al.]{}, that contains $x$. Let $j$ be the index such that $x = c_j$. Define $$\label{eq:definition of f}
    {\psi}(x) {\stackrel{\rm{def}}{=}}\begin{cases}
                    c_{\frac{(n-k)+j}{2}} \circ 1    & j \equiv (n-k) \pmod{2}; \\
                    c_{\frac{(n-k)+j+1}{2}} \circ 0    & j \not\equiv (n-k) \pmod{2}.
                \end{cases}$$

\[claim:f is a bijection\] The mapping ${\psi}$ is a bijection from ${\{0,1\}^{n}}$ to ${\mathcal{B}_{n}}$.

We first show that the range of ${\psi}$ is ${\mathcal{B}_{n}}$. Consider $x \in {\{0,1\}^{n}}$ and let $C = \{ c_k, c_{k+1}, \ldots, c_{n-k}\}$ be the symmetric chain that contains $x$. Suppose that $x = c_j$ for some $k \leq j \leq 