This is similar to Bit flipping algorithm, but the algorithm is a little different. Specifically, we have bit string of length $n$, and we can choose any bit to flip and then we flip also the two surrounding bits, if there are any. So we can either flip three consecutive bits inside or flip the left-most/right-most two bits. For example for $n=3$ we can draw transitions between states in a graph:
Now if we make a graph for $n=2$, the graph splits into two non-connected isomorphic sub-graphs as shown:
The same occurs for $n=2,5,8,11,14$, so I assume it holds for $n=3k+2$. For other $n$'s it is a graph with single connected component. Can we prove that the graph splits for $n\equiv 2 \pmod 3$?
I was trying to find some attribute that is invariant for the bit flipping and show that there are two states with this attribute being different (for $n=3k+2$ that is). This is easy for $n=2$ case as we can see that bits parity is always preserved. However the same does not work for $n=5$: as an example there are two states such as $00100$ and $00010$ that cannot be reached from one another, but bits have the same parity. There is probably some simple argument for this, but I don't see it.
By the way here is a Python code that can be used to generate such graphs, it requires graphviz:
length=5 def flip(N, bit): pattern = 3 if bit == 0 else 7 << bit-1 return (N ^ pattern) & ((1 << length)-1) def binary(n): return format(n, '0%ib' % length)[::-1] from graphviz import Graph dot = Graph() for v1 in range(2**length): for b in range(length): v2 = flip(v1, b) if v1 <= v2: dot.edge(binary(v1),binary(v2),str(b+1)+".") dot.render('graph_complete%i' % length, view=True)