Consider a finite binary string $b$ with at least $2017$ ones. Show that one can insert some plus signs in between pairs of digits such that the resulting sum, when performed in base $2$, is equal to a power of two. Proposed by David Stoner
Problem
Source: 2017 ELMO Shortlist C3
Tags: combinatorics
30.09.2017 21:28
Rough outline of a solution (by David Yang). Replace $2017$ with $n$. For $n=4$, show that from any binary string with four $1$s, you can obtain the numbers $\{4,5,6,8\}$ by inserting plus signs suitably. Now we show that we can obtain every even number in the interval $[n,2n]$. Put delimiters after every fourth $1$. This creates $\dfrac{n}{4}$ partitions. Each partition is a binary string containing $4$ ones. Using our observation above, we can obtain $\{4,6,8\}$ from every partition. The minimum sum we can get using this is $n$ and the maximum sum $2n$. Note that you obtain $2n$ by using $\dfrac{n}{4}$ number of $8$'s. In this sum, replacing every $8$ with a $6$ lessens the sum by $2$, obtaining newer even numbers. You can represent all even numbers down to $\dfrac{n}{4}\times 6 = \dfrac{3n}{2}$. Now, start replacing each $6$ with $4$, and you can represent every even number down to $n$. We are done, since we can now take the power of two in the range $[n,2n]$ and get the desired result. Note: I have done a good bit of hand waving since I assumed no $1$ was left after we placed the delimiters. If there are leftover $1$s, use $5$ in a similar fashion as above. Addendum You can roughly use the same approach to obtain all numbers in the range $[n,c\times 2^{\sqrt{n}}]$. The point is that the statement is meant to be sufficiently weak, and this points towards an analytic approach.
26.05.2019 18:31
If we're left with one $1$ we can reach at the top $8\cdot \left\lfloor\frac n4\right\rfloor+1$ and at the bottom $4\cdot \left\lfloor\frac n4\right\rfloor+1$. In this interval we will find a power of two. If we're left with two $1$ we can reach at the top $8\cdot\left\lfloor\frac n4\right\rfloor+2$ and at the bottom $4\cdot \left\lfloor\frac n4\right\rfloor+2$. In this interval we will find a power of two. If we're left with one $1$ we can reach at the top $8\cdot\left\lfloor\frac n4\right\rfloor+4$ and at the bottom $4\cdot \left\lfloor\frac n4\right\rfloor+4$ (as with three $1$ we can always make them summed to $4$). In this interval we will find a power of two. P.S. Your solution is faster and more transparent than the one from official SL.
18.11.2020 10:07
Solved with willwin4sure. Claim: [Key Claim] For $n\ge 4$, any binary string $b$ with $n$ ones can be inserted by $+$'s to get any number in $[n,2n]$. Proof: Induct on $n$. The hardest part of the problem is checking $n=4,5,6,7$. We omit the entire check, but the idea for $n=7$ for example is that we know ``most'' numbers we want can be made with $n=6$, and then we can add on the last one in various ways. Now, separate $b$ into the concatenation of $b_1$ and $b_2$, where $b_1$ has $n-4$ ones and $b_2$ has 4 ones. By induction, the former can be inserted with $+$'s to get any number in $[n-4,2n-8]$, and the latter to any number in $[4,8]$. Therefore, we can combine these in various ways to get any number in $[(n-4)+4, (2n-8)+8]=[n,2n]$, finishing the induction. $\blacksquare$ Finally, note that there is a power of $2$ in $[n,2n]$ for any $n$, so we are done.
17.05.2024 18:49
idk that's ok or not . the key claim is for $n\ge4$ we can obtain $[n,2n]$: proof: then n=4 case is trivial. now we can see if in our binary string $A$ there is no $10$ it means $A$= $(1111....11)_2$ then $(1111.....1)_2+(1)_2=(100.....00)_2$ now we assume there is one $10$ pair $A=(111.....10.....)_2$ let $x$ be number of 1's before this pair and $y$ 1's after it . we know by strong induction part before and after this pair can make numbers in $[x,2x],[y,2y]$ and the pair can make $[1,2]$ . so we can make $$[1+x+y,2+2x+2y]$$done. I'm sorry if there's grammar mistakes