Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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}$. :-( –  Jyrki Lahtonen Jun 12 '12 at 14:58
    
@JyrkiLahtonen: Consider 1100111, it can be 1100 + 1 + 11 or 1 + 100 + 1 + 1 + 1. I don't see a pattern here. –  Andrew Tomazos Jun 12 '12 at 15:02
    
@JyrkiLahtonen: Also note that 111...1 can always be split 1 + 11...1, as 11..1 will always be $2^k -1$ –  Andrew Tomazos Jun 12 '12 at 15:05
    
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. –  Jyrki Lahtonen Jun 12 '12 at 15:13
    
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. –  Jyrki Lahtonen Jun 12 '12 at 15:26

2 Answers 2

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.

share|improve this answer
    
C is 2 because powers of 2 are always of the form 100..0. So its N -> (as per Q) 100..0 -> 1 + 00..0 = 1 –  Andrew Tomazos Jun 12 '12 at 13:11
    
Yes --- if you can prove what you assert in the question. –  Gerry Myerson Jun 12 '12 at 13:21
    
I just collected some data: pastebin.com/3B2P4asC. It seems there are many different $2^k$ partitionings for any given n. Perhaps we can make an argument that there are so many partitionings ($2^{n-1}$) of an n-bit string - that at least some of them must be powers of 2. Perhaps we can show that each partitioning must vary from the others sufficiently to unavoidably spread over a near power of 2. –  Andrew Tomazos Jun 12 '12 at 14:38

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$.

share|improve this answer
    
You lost me at the very beginning when you introduced $A$ and $B$ without defining them. –  Gerry Myerson Jun 13 '12 at 6:10
    
A(T) looks like the Min(Sum(Parition(T))) and B(T) looks like the Max(Sum(Partition(T))) –  Andrew Tomazos Jun 13 '12 at 6:13
    
Yes, exactly. I edited to try to clarify. –  Zander Jun 13 '12 at 11:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.