ELMO 2017 Shortlist C3

To soar above this world

ELMO 2017 Shortlist C3 Binary String

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.

Source : ELMO-2017-SL

Proof :

记二进制串里 $1$ 的个数有 $n$ 个，则对于 $n\ge17$ 都成立

所有 $[n,\dfrac{3n}{2}]$ 的数都可以表示出来

先在每一个字符后面都加上加号，这样总和为 $n$ ，每次选取一个单独的 $1$ 取消它后面的加号，要求他后面也是个单独的 $0$ 或 $1$

这样每操作一次会 $-1+2=+1$ 的增量，最坏的情况是 $111111$ 只能操作 $\dfrac{n}{2}$ 次，所以 $[n,\dfrac{3n}{2}]$ 一定可以被表示

那如果存在 $2^{k} \in [n,\dfrac{3n}{2}]$ 就解决了

否则一定有 $2^k+1\le n \le \dfrac{2^{k+2}}{3}$

先切断最后的四个 $1$ ，只考虑前面

那现在我们从左到右划分，找到一个 $1$ 就把他和他后面的两个位置连起来成一组

最终会形成 $g$ 个组的和 $l$ 个未划分的，未划分的只能是末尾有两个 $1$ 所以 $l \le 2$ 而 $g \ge4$

而一组的和可能是 $7,6,5,4$ 之一，发现不管怎样，这些和都大于等于原来各自贡献 $v$ 的 $2v+1$

所以最终的总和至少是 $2(n-l-4)+g+l+4=2n-l-4+g$

$2(n-l-4)+g$ 是划分的组中 $1$ 的总贡献 $+l+4$ 是未划分的部分，因为 $l \le2$ 且 $g \ge 4$ 总有 $2n-l-4+g \ge 2n-2 \ge2^{k+1}$

这样只要当和超过了 $2^{k+1}$ 时候就停下，如果刚好等于就结束，否则考虑减去刚划分的组 $1a_1a_2 \rightarrow 4+2a_1+a_3$

和会是 $2^{k+1}-1,2^{k+1}-2,2^{k+1}-3$ 中的一个

如果是 $2^{k+1}-3$ ，那就是把 $1+a_1$ 变成 $1a_1$ 总和增加了 $1$ ，然后拿出来末尾的四个 $1$，把他们的总和从 $4$ 变成 $6$ ，因为 $6 \in [4,\dfrac{3\times4}{2}]$ 所以一定能调整到

如果是 $2^{k+1}-2$ 或者 $2^{k+1}-1$ 直接调整末尾的 $4$ 个 $1$ 即可

实际上这个结论对 $n \le 16$ 的部分也成立

因为 $[1,16]$ 中 $[n,\dfrac{3n}{2}]$ 中没有 $2$ 的整次幂的只有 $5,9,13$ 他们最多能取到 $7,13,15$

如果 $0$ 隔开 $1$ 的段数多于 $\lfloor\dfrac{n}{2}\rfloor$ 就可以多调整几次调整为整次幂

否则的话情况不多，可以暴力枚举