# [seqfan] Re: A puzzle from Emissary

franktaw at netscape.net franktaw at netscape.net
Wed Nov 30 02:20:06 CET 2011

```Here's another approach to the same result.

Given a number with k 1's, 2^(n-1) < k <= 2^n, we show that it is
always possible to obtain 2^n as a sum.

The base case is to have all the ones individually, summing to k.

We can always increase this by using at most 2 of the ones to get a sum
1 larger. Just take any 1 that is not at the end, and make it the first
bit of a two-bit number. Whether the following bit is 0 or 1, the total
has increased by 1.

We can also always use at most 3 of the ones to make the sum 4 larger.
If we have 11x, the resulting 3-bit number is 4 larger than its number
of bits. For 1011, use the final 11 and another bit the same way. If we
have 100, making it a 3-bit number adds 3, and at most 2 more bits are
required to add 1 more (as above). Finally, if we have 1010x, 10 + 10x

It is then a simple combinatorial matter to show that any k can be
increased to the next power of 2 without using up all the bits.