0

A "string" consists only of the characters "A", "B", "C", and "D". An example would be ABBDCA. Another example could simply be "D". The below rules are the only ways for us to change the string:

  1. A substring of AB or BA can be replaced with C and the character C can be replaced with a substring AB or BA.
  2. A substring of BC or CB can be replaced with A and vice versa.
  3. A substring of AC or CA can be replaced with B and vice versa.
  4. A substring of "ABC" can be replaced with the character "D" and vice versa.

How do you rigorously show that you cannot go from the string "A" to the string "B"? How do you show that you cannot get from the string "A" to the string "D"?

What I tried:

If you can get from string "A" to string "B", that must mean you can also get from string "A" to string "AC". If we show that we can't get from string "A" to string "AC" then that must mean we also can't get to string "B". This seems trivial but I can't prove it rigorously. Any ideas?

MathIsCool
  • 23
  • 1
    Consider parity (odd|even) of the number $A$s, $B$s, $C$s and $D$s and the difference between the numbers of each and each step. To change the relative difference in $A$s and $B$ you must invoke rules 2 or 3 and you must do it an odd number of times. Then means you will have an odd number of $C$. To get rid of the $C$s you must invoke 1 or 2 and that puts more restrictions. It's messy and complicated but you can find a rule about combinations of numbers of $A,B,C,D$ and even oddness that if $A$ is acceptable, $B$ will not be. – fleablood Jan 14 '22 at 07:48
  • See also: https://math.stackexchange.com/questions/3557370/olympiad-of-may-2017 . In fact, I think the problem-makers first choose some small group and then make up rules around that! –  Jan 14 '22 at 12:35

1 Answers1

2

With the problems such as this one, the best thing is to find an invariant, which will stay the same whenever a rule is applied. Then you need to make sure the value of the invariant for the string $A$ is not the same as the value of the invariant for the string $B$.

In our case, our invariant will be from the Klein $4$-element group, $V_4$, which is isomorphic to the direct product of two cyclic groups: $C_2\times C_2$, and is abelian (commutative), and also associative (as every group is!).

The multiplication table for $V_4$ is as follows:

$$\begin{array}{c|cccc}\times&e&a&b&c\\\hline e&e&a&b&c\\a&a&e&c&b\\b&b&c&e&a\\c&c&b&a&e\end{array}$$

Now, map $A\to a, B\to b, C\to c,D\to e$ and map every string into the product of the corresponding elements in $V_4$, e.g. map $ABBDCA$ into $a\times b\times b\times e\times c\times a=c$.

Now, notice that $a\times b=b\times a=c$ so replacing $AB$ or $BA$ with $C$ (rule 1) does not change the invariant. The same can be easily seen for all the other rules. Thus, all four rules preserve this invariant.

Remains only to notice that the strings $A$ and $B$ have different invariants, namely $a$ and $b$, respectively. Thus, applying only the above rules we can never convert $A$ to $B$ or vice versa.

Side note: If you are unfamiliar with the group theory, you can still possibly see particular instances of $V_4$ elsewhere. For example, xor of pairs of binary digits, where $e$ is $00$, and $a,b,c$ are $01$, $10$ and $11$ in some order. Or the symmetries of a rectangle which is not a square: apart from identity ($e$), you have two line reflections and a central reflection (which can be $a, b, c$ in some order).

  • 1
    In fact with some effort you can prove that $V_4$ is exactly the invariant that is appropriate: you can change one word into another if and only if they have the same $V_4$-value. In particular, this tells us some easy invariants that don't require any algebra: e.g., the total number of A's and C's (added up) does not change parity under any operation. – Mees de Vries Jan 14 '22 at 10:01
  • 1
    @MeesdeVries True. $A$, $B$ and $C$ commute because, say, $AB\to C\to BA$, Thus they commute with $D$. Also $AA\to ABC\to D$ and similar for $BB\to D, CC\to D$, and again because of commutativity $DD\to ABCABC\to ABBCCA\to ABC=D$ Thus, any string can be converted to a single letter $A$, $B$, $C$ or $D$. –  Jan 14 '22 at 10:55