[seqfan] Re: A puzzle from Emissary

[franktaw at netscape.net]

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 
adds 4.

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.

Franklin T. Adams-Watters

>Andrew Weimholt
>
>I can prove that at most 2 transforms are needed to reach 1. (i.e. 
that C=2).