Suppose there is a 0-1 string of length n. We can perform the following operation on the string:
We can choose two zeros and invert the subsequence between them. The inversion includes the two zeros aswell. For example if the string is 011010, and we choose the first and fourth zeros it becomes 100110. We can also choose just one 0 and turn it into 1.
It can be proved that after some iterations the whole string will only consist of 1s.
So my question is: What is the maximum number of iterations we can perform before it becomes the all 1 string.
My approach was to construct a sequence of iterations that seems to be optimal, but I can't prove that it is.
(Obviously the maximum can be achieved if we start from the all 0 string.)
If the lenght of the string is even, so n is an even number. I would choose the middle 2 bits, and change them to 11 in two iterations $(00 \rightarrow 01 \rightarrow 11)$. After that i would reset the middle by choosing the bits next to these two $(0110 \rightarrow 1001$). So I could the first step again, and so on.
If n is an odd number. Then I would do almost the same. I would convert the middle one into zero, then reset it with the two bits next to it. $( 00000 \rightarrow 00100 \rightarrow 01010 \rightarrow 01110 \rightarrow 10001 \rightarrow 10101 \rightarrow 11011 \rightarrow 11111) $
We can calculate that the number of iterations for this algorithm is:
\begin{cases}
2^{{\frac{n+1}{2}}}-1, & \text{for odd } n \\
2^{\frac{n}{2}}+2^{\frac{n}{2}-1}-1, & \text{for even } n
\end{cases}
So we can conclude that the maximum number of iterations is greater than this amount. But I think this is the maximum, so this sequence of iterations optimal, but I can't prove it.
Could you please give me some hints on how to prove this, or if it is not true, give me a counterexample.
Best Answer
Let $n$ be the length of the word. For even $n$, a working idea is to build a metric for the word so that every transition increases the metric, and so that the strategy you proposed increases the metric in every step exactly by $1$.