8
$\begingroup$

So given any binary string B:

$$b_1 b_2 \dots b_n$$ $$b_i \in \{0,1\}$$

It would seem it is always possible to make a partitioning of B:

$$ b_1 b_2 \dots b_{p_1}|b_{p_1 + 1}b_{p_1 + 2}\dots b_{p_2}|\dots|b_{p_m + 1}b_{p_m + 2}\dots b_n$$ $$= P_0 | P_1 |\dots|P_m$$

such that when $P_i$ is interpreted as the binary representation of an integer then:

$$\exists{k}:\sum_{i=0}^{m}P_i = 2^k$$

For example here is the first few:

1 = 1 10 = 2 1|1 = 2 100 = 4 1|01 = 2 11|1 = 4 1000 = 8 1|00|1 = 2 10|10 = 4 1|0|11 = 4 ... 

Additional examples are here: http://pastebin.com/3B2P4asC

How can we prove this for all binary strings?

  • 0
    Trying induction on the *weight* (= the number of ones), but it doesn't work. The best start I have found is to begin with the observation that with any pattern of weight 3 or 4 gives rise to a sum $=4$. Thus any pattern of weights 6,7 or 8 can be split into two groups given a four for a total of $8$. Continuing this we see that a number of weight in the range 12 to 16 can always be partitioned to yield a total of $16$. Unfortunately this leaves gaps such as weight 5. Five consecutive ones force us to split it $1_2+1111_2=16_{10}$. :-(2012-06-12
  • 0
    @JyrkiLahtonen: Consider 1100111, it can be 1100 + 1 + 11 or 1 + 100 + 1 + 1 + 1. I don't see a pattern here.2012-06-12
  • 0
    @JyrkiLahtonen: Also note that 111...1 can always be split 1 + 11...1, as 11..1 will always be $2^k -1$2012-06-12
  • 0
    I know. I was trying to force that weight five gang to also give me an eight. If that had succeeded, then the weight class 12 to 16 could be extended to 10 to 16 leaving 9 as the next problem kid. If a weight five has a string of two zeros in between, then we get $100+1+1+1+1=8$ or even with a single zero between two ones we can get eight as $101+1+1+1=8$. For the induction step (approximately doubling the set of weights handled) I need 8 specifically as the sum. Because it has to paired with another 8 so that the total is again a power of two.2012-06-12
  • 0
    Actually a better way of helping the problem preventing me from taking the inductive step is to observe that some strings of weight 1 or 2 can also give a 4, and thus paired up with a group of weight 3 or 4. Something's still missing.2012-06-12

2 Answers 2