Matching between bit vector I'm looking for a matching $\left(\vec{b}, \vec{b}'\right)$ among all the bit vectors in $\{0,1\}^n$ such that:

*

*$\left\lVert\vec{b}\right\rVert_1 = n - \left\lVert\vec{b}'\right\rVert_1$

*$\left\lVert\vec{b} - \vec{b}'\right\rVert_1$ is as small as possible.

For example, $\left(\vec{b}, \vec{b}'\right) = \left(\vec{b}, 1 - \vec{b}\right)$ would be a feasible matching, but I do not believe that $\left\lVert\vec{b} - \vec{b}'\right\rVert_1$ would be as small as possible.
 A: For each $k$ such that $k<n/2$, the best possible pairing would have the property that when for each $i$ such that $b_i=1$, you also have $b_i'=1$. That is, the paired vector has ones at all the spots the original does. There indeed exists a pairing which accomplishes this, as described in the answers to this MSE question.
All that remains is to define a pairing for the vectors where exactly half of the positions are ones. Clearly, $\|b-b'\|\ge 2$ for any such pairing; we give a pairing which perfectly achieves this lower bound. Letting $T_n$ be the set of binary vectors of length $n$ with exactly $n/2$ ones (defined when $n$ is even), we will define this pairing on $T_n$ recursively.
Given $b\in T_n$, you first try to find the smallest integer $i$ such that $b_{2i}+b_{2i+1}=1$. There are two cases:

*

*If $i$ exists, then $b'$ is obtained by switching $b_{2i}$ with $b_{2i+1}$ in $b$. For example, if $b=[0,0,1,1,0,0,\color{blue}1,\color{red}0,0,1]$, then $b'=[0,0,1,1,0,0,\color{red}0,\color{blue}1,0,1]$.


*If no such $i$ exists, then $n$ must be a multiple of four, and $b$ must be entirely built from consecutive pairs of zeroes and consecutive pairs of ones. If we collapse each consecutive pair of zeroes into a single zero, and collapse each pair of consecutive ones into a single one, then the resulting vector is an element of $T_{n/2}$. This is where the recursion comes into play; we define the pairing for these vectors using the previously defined pairing for $T_{n/2}$.
