Consider two vectors $(a_1, \dots, a_n), (b_1, \dots, b_n) \in \{0,1\}^n$ such that they both contain an even amount of ones. Is there an easy way to see that the set $\{i: a_i \neq b_i\}$ has even order? I.e., the two vectors are different in an even amount of positions.
I proved it by induction, but I'm looking for something simpler and more intuitive. Thanks.
On
Let $A$ be the total number of $1$s between the two vectors, (i.e., $wt(\vec{a}) + wt(\vec{b})$), which is even since both vectors have an even number of ones. The positions where $\vec{a}$ and $\vec{b}$ both have a $1$ consume an even number $B$ of $1$s (one in each vector). So the total number of $1$s in one vector where the other vector has a zero in the corresponding position is $A-B$, which is even. This is exactly the number of positions where the two vectors differ.
On
Let $w({\bf a})$ be the weight (number of ones) of the binary vector ${\bf a}$
Then, operating in modulo 2, ${\bf c}={\bf a}+{\bf b}$ has ones in the positions where ${\bf a}$,${\bf b}$ differ, zero otherwise. We are interested in the parity of $w({\bf c})$.
But $w({\bf a}+{\bf b})=w({\bf a})+w({\bf b}) -2 k$ where $k$ is the number of indexes where $a_i=b_i=1$.
Hence, if both $w({\bf a})$,$w({\bf b})$ are even, so is $w({\bf c})$.
$\newcommand{\1}{\mathbf{1}}$One possibility: let $\1$ denote the vector where each component is $1$. Note that a binary vector has an even number of $1$'s iff the sum of its elements is even (congruent to $0$ mod $2$). Thus $$\1^T \mathbf{a} \equiv 0\pmod{2}\quad\text{and}\quad \1^T\mathbf{b} \equiv 0\pmod{2}.$$ Hence $$\1^T(\mathbf{a} - \mathbf{b}) \equiv 0\pmod{2},$$ so the vector $\mathbf{a} - \mathbf{b}\in\{0,1\}^n$ (using mod $2$ arithmetic) has an even number of $1$'s. This means that $\mathbf{a}$ and $\mathbf{b}$ differ in an even number of places. (You can show that $a_i - b_i \equiv 1 \pmod{2}$ iff $a_i\ne b_i$, for $a_i,b_i\in\{0,1\}$.)