Problem 1623

### Part (a)

We need to prove that for every solution $(X, Y)$ of a simplified equation, both $X$ and $Y$ can be written in the form of a power of a word like $Z$ (where $Z$ can contain only one alphabetic letter).

1. Assume a simplified equation: Consider a simplified equation $X = Y$. Since $X$ and $Y$ are different words, we can write $X$ and $Y$ as sequences of letters. Let $X = x_1 x_2 \cdots x_m$ and $Y = y_1 y_2 \cdots y_n$ where $x_i$ and $y_j$ are letters of the alphabet.

2. Equal lengths: If $m = n$, then $X = Y$ implies $x_i = y_i$ for all $i$, which contradicts the assumption that $X$ and $Y$ are different words. Therefore, $m \neq n$.

3. **Assume $m > n$**: Without loss of generality, assume $m > n$. Then $X$ can be written as $X = Z^k$ for some word $Z$ and integer $k$ such that $Z$ is a prefix of $X$ and $Y$. Similarly, $Y$ can be written as $Y = Z^l$ for some integer $l$.

4. **Construct $Z$**: Since $X$ and $Y$ are different, $k \neq l$. Therefore, $X = Z^k$ and $Y = Z^l$ where $Z$ is a word consisting of a single letter repeated multiple times.

5. Conclusion: Both $X$ and $Y$ can be written in the form of a power of a word $Z$ where $Z$ contains only one alphabetic letter.

$\blacksquare$

### Part (b)

We need to prove that words $W_1, W_2, \cdots, W_n$ that are the answers of a simplified equation can be produced with fewer words.

1. Consider the rightmost words: Consider the rightmost words on either side of the equation, say $W_i$ and $W_j$. If both have equal length, they are equal, and we are done.

2. Unequal lengths: Assume $W_i$ is longer than $W_j$. We can re-express $W_i$ as $W_i'W_j$ and substitute this back into the equation, replacing all copies of $W_i$ to yield $\ldots W_i'W_j = \ldots W_k W_j$.

3. **Cancel $W_j$**: Cancel $W_j$ from each side to get another simplified equation in $n$ words, $\ldots W_i' = \ldots W_k$.

4. Repeat the process: Repeat this process until the rightmost words on each side are of equal length, allowing us to equate them and express the substituted words in the form of $n-1$ words.

5. Conclusion: Reversing the substitutions lets us express the original $n$ words in terms of these $n-1$ words.

$\blacksquare$

### Part (c)

We need to prove that $n$ words $W_1, W_2, \cdots, W_n$ that are the answers of a simplified system of equations can be produced with at most $c$ words, where $c$ is the number of connected components of the graph $G$.

1. **Construct graph $G$**: Define graph $G$ with vertices $\{1, 2, \cdots, n\}$ such that $i$ and $j$ are connected if in one of the equations, $W_i$ and $W_j$ appear on the right side of each side of the equation.

2. Spanning tree: Consider a spanning tree of each component of $G$. Delete all equations whose edges are not in a spanning tree. Now there are $n-c$ edges in total, so $n-c$ remaining equations.

3. Algorithm from part (b): Pick one of the equations and perform the algorithm from part (b) on it. This lets you express $W_1, \ldots, W_k$ in terms of fewer words, say $W_1', \ldots, W_{k-1}'$.

4. Group vertices: Group the vertices of $G$ into $k$ groups: one group for the vertices representing words which become expressed in the form $\ldots W_i'$ for each $1 \leq i \leq k-1$, and one group for the remaining vertices.

5. **Construct new graph $G'$**: Construct a graph $G'$ that corresponds to the situation after all the $W_1, \ldots, W_k$ have been replaced by all the $W_1', \ldots, W_{k-1}'$. This graph will have $k-1$ vertices representing the words $W_1', \ldots, W_{k-1}'$, as well as $n-k$ vertices representing the unaffected words.

6. Number of components: Show that the number of components of $G'$ is at most $c$. Each group contains at least one vertex, and the new graph $G'$ is identical to the original $G$ except that the two vertices representing $W_i$ and $W_j$ are merged into one new vertex.

7. Repeat the process: Repeat this process until we get $c$ isolated vertices. Reversing the substitutions, we can express the $n$ words in terms of $c$ words.

$\blacksquare$