Bit placement puzzle 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? 
 A: 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}}.
$$
