0
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ Try formulating this problem in terms of linear algebra over GF(2) (the field with two elements). This will answer some of your questions. $\endgroup$ – Yuval Filmus Feb 20 '17 at 12:56
  • $\begingroup$ Yes, exactly so. $\endgroup$ – Yuval Filmus Feb 20 '17 at 13:31
  • $\begingroup$ 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. $\endgroup$ – D.W. Feb 20 '17 at 23:49
1
$\begingroup$

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):

You can find that solution using linear algebra in modulo 2 arithmetic (i.e., Gaussian elimination modulo 2).

$\endgroup$

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.