# Minimum # toggle (3 consecutive elements) operations to convert ring A into ring B (rings made of Xs and Os: X->O and O->X)

There is a ring A and ring B made of Xs and Os. My aim is to convert A to B by using only the minimum number of # operations. When I do # on an element i of the ring, element i-1, i and i+1 will be toggled. (toggled => X->O and O->X).

• Try formulating this problem in terms of linear algebra over GF(2) (the field with two elements). This will answer some of your questions. – Yuval Filmus Feb 20 '17 at 12:56
• Yes, exactly so. – Yuval Filmus Feb 20 '17 at 13:31
• Nice exercise! Where did you run across it? I encourage you to credit the source of the problem. Also, what have you tried? If you still can't solve it after a day or two of trying, edit the question with this information and then ping me. – D.W. Feb 20 '17 at 23:49

You can represent a ring as a $n$-bit string, where $n$ is the number of positions in the ring. Encode an X as 1, and encode a O as 0 (zero). That gives you a $n$-bit string, say $x$.
The # operation on index $i$ corresponds to xor-ing the string representing the current state of the ring with the string $c_i = 0^{i-1} 111 0^{n-i-3}$. In other words, if the ring is currently $x$, then the # operation on index $i$ changes the state of the ring to $x \oplus c_i$.
Suppose you're given two rings $x,y$ and you want to find a way to transform $x$ into $y$. Then all you need to do is find a subset of $c_1,\dots,c_n$ whose xor is equal to $x \oplus y$. This will be the solution to your problem. Can you see how to do that? Solution below (don't mouse over until you've thought about it for a while):