Sum(Partition(Binary String)) = $2^k$

Question

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?

Answer 1

This is (essentially) problem 6 in the MSRI newsletter, Emissary, for Fall 2011:

You are allowed to transform positive integers $n$ in the following way. Write $n$ in base 2. Write plus signs between the bits at will (at most one per position), and then perform the indicated additions of binary numbers. For example, $123_{10} = 1111011$ can get + signs after the second, third and fifth bits to become $11+1+10+11 = 9_{10}$; or it can get + signs between all the bits to become $1+1+1+1+0+1+1 = 6_{10}$; and so on. Prove that it is possible to reduce arbitrary positive integers to 1 in a bounded number of steps. That is, there is an absolute constant $C$ such that for any $n$ there is a sequence of at most $C$ transformations that starts with $n$ and ends at 1. Comment: The best possible bound is a real shocker.

No solution is given.

Answer 2

Look at two and three bit strings starting with 1, and the minimum and maximum ways they can contribute to the sum. $$ \begin{array}{c|c|c} T & A(T) & B(T) \\ \hline \\ 1 & 1 & 1 \\ 10 & 1 & 2 \\ 11 & 2 & 3 \\ 100 & 1 & 4 \\ 101 & 2 & 5 \\ 110 & 2 & 6 \\ 111 & 3 & 7 \end{array} $$ For example, we can count 110 as $1+1+0=A(110)$ or as $6=B(110)$ (the only other possibilities are $1+2$ and $3+0$). So for the two-bit strings $B(T)=A(T)+1$, and for the three-bit strings $B(T)-A(T)\in\{3,4\}$.

Now consider a number $k$ and let $w(k)\ge 6$ be the number of 1 bits in its binary representation.

Split $k$ into components like this: $$ (k)_2 = T_1 0^* T_2 0^* T_3 \ldots T_{c+3} 0^* T_{end} $$ where each $T$ starts with 1, each of $T_1,T_2,T_3$ has exactly two bits, and each of $T_4,\ldots,T_{c+3}$ has exactly three bits, and $T_{end}$ can be empty or can contain 1,10 or 11 if $(k)_2$ ends that way without allowing another 3-bit term. In other words, gather terms in a greedy fashion starting with the next available 1-bit taking two or three bits as required, skipping extra zeros, and assigning the left-over to $T_{end}$. For example $$ (999999)_2 = 11~~11~~0~~10~~000~~100~~0~~111~~111 $$ so for $n=999999$ we would get $$T_1=T_2=11,T_3=10,T_4=100,T_5=111,T_6=111,c=3,T_{end}=\text{empty}$$

For each type of term $A(T)$ counts the bits in $T$, so $\sum A(T_i) = w(k)$ (including $T_{end}$ in the sum). Now we can use our terms as a counter as follows.

• Start counting each term with $A(T)$ to sum to $w(k)$.
• To increment, count $T_1$ as $B(T_1)$ to get $w(k)+1$.
• Count $T_2$ as $B(T_2)$ to get $w(k)+2$.
• Count $T_3$ as $B(T_3)$ to get $w(k)+3$.
• Count $T_4$ as $B(T_4)$ and reset to $A(T_i),i=1,2,3$ to get either $w(k)+3$ or $w(k)+4$.

Repeat this, counting more 3-bit terms as $B(T)$ to add 3 or 4 at a time (and finally $B(T_{end})$ if applicable), counting $T_1,T_2,T_3$ as $A$ or $B$ to get the increments in between. By this counting method we find partitions that sum to each number between $w(k)=\sum A(T_i)$ and $\sum B(T_i)$.

Let $z$ be the number of terms that are $T=111, A(T)=3, B(T)=7$. Then $$ \begin{align} w(k) = \sum A(T_i) & \le 6+(2c+z)+2 \\ w(k)-8 & \le 2c+z \le 3c \\ c & \ge w(k)/3-8/3 \\ \sum B(T_i) & \ge \sum A(T_i)+3+3c+z \\ & \ge w(k)+3+w(k)/3-8/3+w(k)-8 \\ & = 7w(k)/3-23/3 \end{align} $$

So for any $k$ we can find a partition that sums to each value in $[w(k),\max(w(k)+3,7w(k)/3-23/3)]$. For all $w(k)\ge 6, w(k)\ne 9, w(k)\ne 10$ this interval contains a power of 2.

We handle the remaining possible values for $w(k)$ as special cases.

For $w(k)=10$ we can just use a refinement of the bound above. In this case $c\ge 1$, so $\sum B(T_i) \ge \sum A(T_i)+6$, so 16 will be included.

$w(k)=1,2,4$ are immediate, just add the bits. For $w(k)=3$ we can always partition the number into $10,1,1$ or $11,1$ and possibly some zeros. For $w(k)=5$ if all 1 bits are adjacent, we can write it as $1111,1$, otherwise we can write it as $101,1,1,1$ or $100,1,1,1,1$.

For $w(k)=9$ if all bits are adjacent, then we can take $11111111,1$. Otherwise there is either a 100 or 101 which we take as $T_1$. From the remaining bits make a three-bit term $T_2$ and a two-bit term $T_3$. Then either $B(T_1)+B(T_2)$ or $B(T_1)+B(T_2)+B(T_3)$ plus the remaining bits makes 16.

This answers the original question.

As an addendum, we can extend this technique taking longer terms, e.g. for 4-bit terms $A(T)+7 \le B(T) \le A(T)+11$, so we can take 11 two-bit terms and $c$ 4-bit terms and count from $w(k)$ to at least $w(k)+11+7c$.

For 5-bit terms $A(T)+15 \le B(T) \le A(T)+26$ and with 26 two-bit terms we can count from $w(k)$ to $w(k)+26+15\lfloor (w-26)/5\rfloor$. For $w(k)$ large enough this upper bound is larger than $3w(k)$, so the interval will contain a power of 3.

Carrying it further, taking $l$-bit terms for larger $l$ we can extend this interval to any multiple of $w(k)$. Thus, for choice of any $q>1$ there is a bound $W(q)$ so that any number $k$ with Hamming weight large enough $w(k)>W(q)$ can be partitioned into $P_i$ with $\sum P_i = q^m$ for some $m$.