Partitioning binary strings by total parity

Question

If I have a binary string $\underline{a} = (a_1 \, a_2 \,\ldots\, a_N)$ where $a_i \in 0,1$ and I partition the set of all such strings $A$ by the total parity of the string, $A = \Pi_0 + \Pi_1$ where $\Pi_0$ and $\Pi_1$ are the subset of strings with total parity 0 and 1 respectively $$ \textrm{i.e. } \left( \sum_k a_k \right) \textrm{ mod } 2 = p \textrm{ for all } \underline{a} \in \Pi_p \, , $$ is the function where I change the value of the first element, $$ M[\, \underline{a} \,] = M[\, (a_1 \, a_2 \,\ldots\, a_N) \,] = (\overline{a_1} \, a_2 \,\ldots\, a_N) \,, $$ a bijection between the two subsets, $ M : \Pi_0 \rightarrow \Pi_1$?

Answer 1

For a bijection,

• each element of X must be paired with at least one element of Y, and each element of Y must be paired with at least one element of X,
  • $M(\underline{a}) $ always maps to an element in the other partition
• no element of X may be paired with more than one element of Y, and no element of Y may be paired with more than one element of X.
  • $M(M(\underline{a}))= \underline{a}$ guarantees a unique partner in the other partition, since every element is recovered by a second application of the function (no loss of domain)