0
$\begingroup$

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:

enter image description here

Now if we make a graph for $n=2$, the graph splits into two non-connected isomorphic sub-graphs as shown:

enter image description here

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$?

My attempts:

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)
$\endgroup$
1
$\begingroup$

Almost complete solution, or at least a very broad hint

This is a 1D version of the game "lights out". Philip Klein in his book on The Matrix in Computer Science has a nice analysis for the 2D case that should apply here. But the gist is this:

Start from any bit vector in $F^k$ where $F$ is the field of 2 elements. Applying an operation amounts to adding to it one of the $k$ vectors $$ \pmatrix{1&1&0&\ldots& 0} \\ \pmatrix{1&1&1&\ldots& 0} \\ \pmatrix{0 & 1&1&1&\ldots& 0} \\ \pmatrix{0 & 0 & 1&1&1&\ldots& 0} \\ \vdots\\ \pmatrix{0 & \ldots&1&1&1& 0} \\ \pmatrix{0 & \ldots & 0 &1&1&1} \\ \pmatrix{0 & \ldots & 0 &0&1&1} \\ $$ so you can put these in a matrix, row-reduce it, and compute its rank. If the rank is not $k$, then not every target bit-vector is reachable from the all-zero vector, and your graph has at least two components.

Row reduction for this matrix appears to be relatively simple and methodical. Give it a shot.

$\endgroup$
  • $\begingroup$ I see, so any linear combination of these equals to any reachable state, looks simple. Will try the row reduction, thanks for tip. $\endgroup$ – Sil Apr 20 at 12:09
1
$\begingroup$

Based on @JohnHughes answer, I was able to prove this. Basically the matrix corresponding to the vectors is actually a Tridiagonal matrix, for which determinant is well known and is given by recurrence formula $$ f_n=f_{n-1}-f_{n-2}\, ,f_0=1\, , f_{-1}=0 $$ which gives a sequence of (starting from $n=1$) $$ 1,0,-1,-1,0,1,1,0,-1,-1,\dots $$ which can be easily seen to be $0$ for $n=3k+2$, so there the rank of the matrix is $<n$ and not all states can be reachable by these linear combinations.

$\endgroup$
  • $\begingroup$ While everything you say is correct, there's a subtlety here: it's possible that the determinant could be nonzero in every case, while the matrix you care about actually has a kernel. How can that be? The determinant calculation is over the reals, while the matrix has entries in $F_2$, the field of two elements. If the determinant pattern had been say, $1, 2, -1, -1, 2, 1, 1, 2, -1, -1,\ldots$, then you might have been tempted to say "the matrix is full rank, so the problem is solvable", but over $F_2$, it's not full-rank at all. In short: when thinking about $F_2$, best ignore determinants. $\endgroup$ – John Hughes Apr 20 at 23:43
  • $\begingroup$ @JohnHughes Can't we evaluate the determinant in the $F_2$ as well, so it would be in this case $1, 0, 1, 1, 0, 1, 1, 0, 1, 1,\ldots$? Although I don't know if the same property holds then (having full rank iff determinant is not zero), I guess you are saying this does not hold then? $\endgroup$ – Sil Apr 21 at 8:32
  • $\begingroup$ No -- I'm saying that you used the determinant in $\Bbb R$, and its relation to $\Bbb R$-rank, apparently without considering whether reducing to $F_2$ after the fact was valid or not. I honestly know relatively little about $F_2$ vector spaces, but there's definitely some weird stuff there, like that the polarization identity doesn't work to relate the inner product to the norm. To say whether "$\det = 0$ iff the rank is deficient", I'd want to work through the whole proof, and I haven't done that. $\endgroup$ – John Hughes Apr 21 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.