Disjoint subsets and Number of 1's in the binary representation

Question

For a subset $S$ of $[n]$, let $\chi(S)$ denote the $n$ bit 'characterisitc vector' of $S$, i.e., $\chi(S)=(a_1, a_2, \ldots, a_n)$ where $a_i=1$ if $i \in S$ and $a_i=0 $ if $i \notin S$. Think of $\chi(S)$ as an $n$ bit binary number and let $D(\chi(S))$ denote the decimal representation of $\chi(S)$.

Let $A, B \subseteq [n]$. The question is to show that $A \cap B = \varnothing$ if and only if the number of 1's in the binary representation of $D(\chi(A))+ D(\chi(B)) = |A|+|B|$.

I could prove the forward direction: Observe that $D(\chi(S))= \sum_{i \in S} 2^{n-i}$ and the number of 1's in $\chi(S)= |S|$.

Then if $A \cap B = \varnothing$, $$D(\chi(A))+ D(\chi(B)) = \sum_{i \in A} 2^{n-i} + \sum_{i \in B} 2^{n-i} = \sum_{i \in A \cup B} 2^{n-i} = D(\chi(A \cup B))$$

Then

\begin{equation} \begin{split} \text{number of 1's in the binary representation of }\ D(\chi(A))+D(\chi(B)) \\ = \text{number of 1's in the binary representation of}\ D(\chi(A \cup B)) = \text{number of 1's in}\ \chi(A \cup B) = {|A \cup B|} =|A|+|B| \end{split} \end{equation}

To prove the converse, we have, \begin{equation} \begin{split} D(\chi(A))+ D(\chi(B)) & = \sum_{i \in A} 2^{n-i} + \sum_{i \in B} 2^{n-i} \\ &= \sum_{i \in A \cup B} 2^{n-i} + \sum_{i \in A \cap B} 2^{n-i} \\ &= D(\chi(A \cup B))+ D(\chi(A \cap B)) \end{split} \end{equation}

But I don't quite see how to reach the conclusion from here. Hints will be appreciated.

Answer 1

Let $B(n)$ be the number of ones in the binary representation of the integer $n$.

We have to show that if $a\&b\neq0$, $B(a+b)<B(a)+B(b)$.

Imagine we've set up the addition in the normal way:$$\begin{array}{rrrrrrr}&1&0&1&0&1&0\\+&0&1&1&1&0&1\\\hline&\end{array}$$

Let $B'(a), B'(b), B'(a+b)$ be the number of ones encountered so far while performing the addition: that is, in the columns to the right of an imaginary vertical line.

Performing the addition from right to left, $B'(a+b)$ will continue to equal $B'(a)+B'(b)$ so long as we only encounter ${0\atop0}$ or ${0\atop1}$ or ${1\atop0}$.

As soon as we meet ${1\atop1}$, we have to write $0$ in the sum. This causes $B'(a+b)$ to start lagging by $2$. Then three things can happen:

• The next thing we have to add is $0\atop0$. Then we write down the carry bit, and from now on, things proceed in a carryless state (as though we were starting afresh to the left of the line), but with $B'(a+b)$ lagging by $1$.
• The next thing we have to add is $0\atop1$ or $1\atop0$. Then we have to write down another $0$ in the sum, so $B'(a+b)$ is lagging by an extra $1$.
• The next thing we have to add is $1\atop1$. Then we write down $1$ in the sum, so again $B'(a+b)$ is lagging by an extra $1$.

Sooner or later we reenter the carryless state, but if $B'(a+b)$ ever lags by $2$ or more, only one point can be restored; there is no way to make up the lost ground.