[seqfan] Re: A puzzle from Emissary

[franktaw at netscape.net]

I should have noted that k=5 is a special case. You can't get 8 from 
11111, but you can get 16, and you can get 8 from any other odd number 
with 5 ones.

(The argument below fails for k=5 at the last step; adding even a 
single 4 makes the total too big, and you can't in general add more 
than two ones.)

Franklin T. Adams-Watters

-----Original Message-----
From: franktaw <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).


_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/