Bit placement puzzle

Question

Consider a binary vector of length $n$ that is initially all zeros. You choose a bit of the vector and set it to $1$. Now a process starts that sets the bit that is the greatest distance from any $1$ bit to $1$ (or an arbitrary choice of furthest bit if there is more than one). This happens repeatedly with the rule that no two $1$ bits can be next to each other. It terminates when there is no more space to place a $1$ bit. The goal is to place the initial $1$ bit so that as many bits as possible are set to $1$ on termination.

Say $n =2$. Then wherever we set the bit we end up with exactly one bit set.

For $n =3$, if we set the first bit we get $101$ in the end. But if we set the middle bit we get $010$ which is not optimal.

For $n=4$, whichever bit we set we end up with two set.

For $n=5$, setting the first gives us $10101$ with three bits set in the end.

For $n=7$, we need to set the third bit to get $1010101$ it seems.

What is the simplest rule for placing the initial bit which will always give an optimal answer?

Answer 1

First consider the number of bits that will be turned on by this process in a string of $n$ zeroes flanked by ones. Call that number $A_n$. Clearly $A_1=A_2=0$, and for $n\ge 3$ the following recursion holds: $$ A_n = 1+A_{\lfloor (n-1)/2\rfloor}+A_{\lceil (n-1)/2 \rceil}, $$ or $$\begin{eqnarray}A_{2k+1}&=&1+2A_{k} \\ A_{2k+2}&=&1+A_{k}+A_{k+1}\end{eqnarray}$$ for $k\ge 1$. Now consider $B_n$, the number of bits that will be turned on in a string of $n$ zeroes with a single flanking one. Here $B_{n}=1+A_{n-1}$ for $n\ge 2$, so we find the following: $$\begin{eqnarray} B_{2k+2}&=&1+A_{2k+1}&=&2+2A_{k}&=&2B_{k+1} \\ B_{2k+3}&=&1+A_{2k+2}&=&2+A_{k}+A_{k+1}&=&B_{k+1}+B_{k+2}\end{eqnarray}$$ for $k\ge 1$. (The sequence starts with $B_{0}=B_{1}=0$ and $B_{2}=B_{3}=1$.) The original problem asks for $i \in \{1,2,\ldots,n\}$ such that $B_{i-1}+B_{n-i}$ is maximized. Studying the sequence $B_n$, one sees efficient packing ($B_n=n/2$) when $n$ is a power of $2$, and inefficient packing ($B_n=n/3$) when $n$ is three times a power of $2$. A reasonable "greedy" conjecture, then, is that forcing the largest possible string of bits into an efficient packing structure, by choosing $$i=2^{\lfloor \log_2(n-1)\rfloor}+1,$$will produce an efficient overall packing; at any rate, it guarantees a packing fraction of $5/12$, since no more than half of the bits are suboptimally packed.

This conjecture seems to hold up numerically; at least for $n\le 10000$, an optimal packing is produced by this choice of $i$. This choice would seem risky when $n=2^k+3\cdot 2^{k-2}+1$, since the leftover portion is large and its packing is as poor as possible. Indeed, such values of $n$ have an unusually large number of equally good choices for $i$ (unlike, say, $n=2^k+2^{k-2}+1$); but the simple choice above is always tied for first.

---

A closed-form expression for the number of bits that will be set for a given $(i, n)$ is provided by section 3.3 of this paper on the "urinal problem" (which is essentially what this puzzle is). In terms of the auxiliary function $$K_n=2^{\lfloor\log_2 n\rfloor},$$ which is the largest power of $2$ not greater than $n$, they give the following correct expression for my $B_n$: $$ B_{n} = \frac{1}{2}K_n + \left(\left\lfloor\frac{2n}{K_n}\right\rfloor - 2\right)\cdot\left(n - \frac{3}{2}K_n\right). $$ The expression $\lfloor{2n / K_n}\rfloor - 2$ is either equal to $1$ (if $n$'s binary representation starts with $11$) or $0$ (if it starts with $10$), and so $B_{n}$ itself is either $n - K_n$ or $K_n / 2$. If $n$ is a power of $2$, then clearly $B_{n}=K_n/2=n/2$ exactly.

Now, when the initial bit is placed in the $i$-th position, the total number of bits that will be turned on is $1 + B_{i-1} + B_{n-i}$. My conjecture is that setting $i=K_{n-1}+1$ will always produce an optimal packing; the number of bits that will be set is then $$ 1 + B_{K_{n-1}} + B_{n-1-K_{n-1}}. $$ Because $K_{n-1}$ is a power of $2$, this can also be written as $$ 1 + \frac{1}{2}K_{n-1} + B_{n-1-K_{n-1}}. $$

Answer 2

Let $A(k)$, $B(k)$, $C(k)$ be the number of moves if the game starts with $\underbrace{0\ldots0}_k$, $1\underbrace{0\ldots0}_k$, or $1\underbrace{0\ldots0}_k1$, respectively (with $k\ge1$ for the $C$ case so that we start in a legal position). Clearly $A(0)=0$, $A(1)=1$, $B(0)=B(1)=0$ and also $C(1)=C(2)=0$. For larger values of $n$ we have the recursions $$ \begin{align}A(n)&=1+\max_{0\le k< n}(B(k)+B(n-k-1))\\ B(n)&=1+C(n-1)\\ C(2n+1)&=1+2C(n)\\ C(2n)&=1+C(n)+C(n-1)\\ \end{align}$$ So first we should find $C(n)$. By numerical experiments, $C(n)$ seems to grow one by one except that values of form $2^k-1$ are repeated $2^{k}+1$ times. We can cast this more precisely into the following

Lemma. $$\tag1 C(n) =\begin{cases}0&\text{if }n\in\{1,2\},\\ \min\{n-2^{k+1},2^{k+1}-1\}&\text{if }k=\lfloor\log_2\tfrac n3\rfloor \text{ (i.e. }3\cdot 2^k\le n<3\cdot2^{k+1}\text{)}.\end{cases}$$ We can see this by induction: For $n\in\{1,2,3\}$ we check (1) immediately. For even $n=2m>3$ with $3\cdot 2^k<n<3\cdot 2^{k+1}$ we have $$\begin{align}C(n)&=1+C(m)+C(m-1)\\&= 1+\min\{m-2^{k},2^{k}-1\}+\min\{m-1-2^{k},2^{k}-1\}\\&=\begin{cases}1+m-2^{k}+m-1-2^{k}&\text{if }m-2^{k}\le 2^{k}-1\\ 1+2^{k}-1+2^{k}-1&\text{if }m-2^{k}\ge2^{k}\end{cases} \\&=\begin{cases}n-2^{k+1}&\text{if }n-2^{k+1}\le 2^{k+1}-2\\ 2^{k+1}-1&\text{if }n-2^{k+1}\ge2^{k+1}\end{cases}\end{align}$$ (note that $n-2^{k+1}=2^{k+1}-1$ can't happen) and if $n=3\cdot 2^k$ with $k\ge1$ we have $$\begin{align}C(n)&=1+C(m)+C(m-1) \\ &= 1+\min\{3\cdot 2^{k-1}-2^{k},2^{k}-1\}+\min\{3\cdot 2^{k-1}-1-2^{k},2^{k}-1\}\\ &=1+2^{k-1}+2^{k-1}-1=2^{k}=n-2^{k+1}\end{align}$$ as needed. And for odd $n=2m+1$ with $3\cdot2^k\le n<3\cdot2^{k+1}$ we have $3\cdot2^{k-1}\le m<3\cdot 2^k$ and hence $$C(n)=1+2C(m)=1+2\min\{m-2^{k},2^{k}-1\}=\min\{1+2(m-2^{k}),1+2(2^{k}-1)\}=\min\{n-2^{k+1},2^{k+1}-1\}$$ also in this case. $_\square$

Now we immediately obtain

Corollary. $$B(n)=\begin{cases}0&\text{if }n\in\{0,1\},\\ 1&\text{if }n\in\{2,3\},\\ \min\{n-2^{k+1},2^{k+1}\}& \text{with }k=\lfloor\log_2\tfrac {n-1}3\rfloor\text{ if }n>3.\end{cases}$$ If $n>1$ then $\frac n3\le B(n)\le \frac n2$ with equality on the left iff $n$ is three times a power of two and equality on the right iff $n$ is a power of two.

Proof: The formula for $B$ follows immediately from the lemma and $B(n)=1+C(n-1)$. For $n>3$ note that $k=\lfloor\log_2\tfrac {n-1}3\rfloor$ implies $3\cdot 2^k\le n-1<3\cdot 2^{k+1}$, i.e. $n=3\cdot 2^k+r$ with $1\le r\le 3\cdot 2^k$. Next $B(n)=n-2^{k+1} = 2^k+r$ if $r\le 2^k$ and then $\frac{n}{B(n)}=\frac{3\cdot 2^k+r}{2^k+r}$ is between $\frac{4\cdot 2^k}{2\cdot2^k}=2$ and $\frac{3\cdot 2^k}{2^k}=3$. And $B(n)=2^{k+1}$ if $2^k\le r\le 3\cdot 2^k$ and then $\frac{n}{B(n)}=\frac{3\cdot 2^k+r}{2\cdot 2^k}$ is between $\frac{3+1}{2}=2$ and $\frac{3+3}{2}=3$. This shows the inequality for $n>3$, the cases $n=2$ and $n=3$ can be checked manually. We also see from the argument that $\frac{n}{B(n)}=2$ and $\frac{n}{B(n)}=3$ occur only for $r=2^k$ and $r=3\cdot 2^k$, respectively. $_\square$

The most important aspect of the corollary is: $B(n+1)-B(n)$ is either $0$ or $1$. Therefore, when determining $a, b$ such that $a+b=n-1$ and $A(n)=1+B(a)+B(b)$ we observe that we may replace $a$ with $a+1$ (and $b$ with $b-1$) if $3\cdot 2^k\le a<4\cdot 2^k$ (and $a<n-1$) as that leaves $B(a)$ unchanged and hence cannot decrease the value of $B(a)+B(b)$. On the other hand, if $4\cdot 2^k<a\le 6\cdot 2^k$, then decreasing $a$ increases $B(a)$ and hence cannot decrease the value of $B(a)+B(b)$. If we start with an otimal pair $(a,b)$ with $a\ge b$, this procedure leads to another optimal pair where $a$ has become a power of two, $a=4\cdot 2^k$. In this process, $a$ may have become $<b$ or remained $\ge b$. In the second case when $a\ge b$, we have that $a$ is the largest power of two $\le n-1$. In the first case, the initial $a\ge b$ was $<6\cdot 2^k$, which means that $8\cdot 2^k<n-1<12\cdot 2^k$, so $4\cdot 2^k<b<8\cdot 2^k$. If $4\cdot 2^k<b\le 6\cdot 2^k$, we obtain $B(a)+B(b) = 2^{k+2}=B(8\cdot 2^k)\le B(8\cdot 2^k)+B(n-1-8\cdot 2^k)$ and by maximality $B(n-1-8\cdot 2^k)=0$, i.e. $n$ is slightly above a power of two and we may as well pick $a=8\cdot 2^k$. If on the other hand $6\cdot 2^k<b<8\cdot 2^k$, we may swap $a$ and $b$ and repeat the above procedure, this time at most increasing $a$ so that we end up in the second case again. In summary, we may assume wlog. that $a$ is the largest power of two $\le n-1$ and thus have proved

Theorem. For $n=2^k+r+1$ with $0\le r<2^k$, we have $$ A(n)=1+B(2^k)+B(r)=1+2^{k-1}+B(r). _\square$$

If $r>1$ in the theorem and we write it as $c\cdot 2^m$ with $3\le c<6$, then $B(r)=(c-2)2^m$ if $3\le c\le 4$ and $B(r)=2\cdot 2^m$ if $4\le c<6$. From $2^k>r$ we have $m\le k-2$ in the first case and $m\le k-3$ in the second case. So in the first case we find $$\frac{n-1}{A(n)-1}=\frac{2^k+c2^m}{2^{k-1}+(c-2)2^m}\le\frac{2^k+3\cdot 2^{m}}{2^{k-1}+2^{m}}\le \frac{2^k+3\cdot2^{k-2}}{2^{k-1}+2^{k-2}}=\frac 73.$$ And in the second case we find $$ \frac{n-1}{A(n)-1}=\frac{2^k+c2^m}{2^{k-1}+2^{m+1}}\le \frac{2^k+6\cdot 2^m}{2^{k-1}+2\cdot 2^{m}}\le\frac{2^k+3\cdot 2^{k-2}}{2^{k-1}+2^{k-2}}=\frac{7}{3}$$ as well (a slight improvement over a more straightforward estimate giving $\frac{n}{A(n)}\le \frac{12}5$).