What is the minimum $k$ such that $\sum_{i = 1}^{k}2^{a_i} = \sum_{j = 1}^{n}2^{w_j}$

Question

Suppose you have a sequence of numbers $S = (w_1,...,w_n)$ and you want to know the minimum $k$ such that $2^{a_1}+...+2^{a_k} = 2^{w_1}+...+2^{w_n} = T$. I'm told that the minimum $k$ is equal to the number of set bits in the binary representation of $T$, but I'm really struggling to intuitively see why this is true and furthermore how to prove that it is true.

Answer 1

Given $(w_1,\ldots,w_n)$, writing the number $T=\sum_{i=1}^n2^{w_i}$ in binary comes down to finding a subset $\{a_1,\ldots,a_k\}\subset\Bbb{N}$ satisfying $$T=\sum_{j=0}^n2^{a_j}.$$ Given that the $w_i$ are positive integers, there is precisely one such subset. That is to say, the number $T$ has a unique binary representation. The $a_j$ are the positions of the $1$s in the binary representation of $T$, so $k$ is the number of $1$s in the binary representation of $k$.

Answer 2

You are given $T$, a positive integer.

Suppose $\sum_{i=1}^k 2^{a_i} = T$. We will show that the $a_k$ may be taken to be strictly increasing. It is clear that we can assume the $a_k$ to be non decreasing.

If the $a_i$ are not strictly increasing, suppose $i$ is the largest index such that $a_i = a_{i+1}$. Then we can replace the partial sum $2^{a_i}+2^{a_{i+1}}$ by $2^{a_i+1}$, hence we have reduced the length by 1. By reordering and repeating as necessary, we see that we can assume the $a_i$ to be strictly increasing.

Now suppose $\sum_{i=1}^k 2^{a_i} = \sum_{i=1}^{k'} 2^{b_i}$, where both the $a_i,b_i$ are strictly increasing. Suppose $a_k < b_{k'}$, then $\sum_{i=1}^k 2^{a_i} \le \sum_{j=0}^{b_{k'}-1} 2^{j} = 2^{b_{k'}} -1 < 2^{b_{k'}} \le \sum_{i=1}^{k'} 2^{b_i}$, a contradiction. Hence $a_k = b_{k'}$. By subtracting $2^{b_{k'}} $ from both sides and repeating, we see that $k=k'$ and $a_i = b_i $ for all $i$.

In particular, there is exactly one strictly increasing sequence $(a_1,...,a_k)$ such that $\sum_{i=1}^k 2^{a_i} = T$. The $a_i$ are the positions of the one bits in the binary representation of $T$.