Show why the following post's correspondence problem is unsolvable

Question

We have the following pairs of strings. $$\begin{bmatrix} aa\\b \end{bmatrix} \begin{bmatrix} ba\\baa \end{bmatrix} \begin{bmatrix} aba\\a \end{bmatrix}$$

The problem is now, to find a concatenation of those pairs, such that the resulting string of the upper row equals the string of the lower row. E.g. if $$\begin{bmatrix} aa\\aab \end{bmatrix} \begin{bmatrix} bb\\ba \end{bmatrix} \begin{bmatrix} abb\\b \end{bmatrix}$$

The solution would be 'aabbaaabb' $$\begin{bmatrix} aa\\aab \end{bmatrix} \begin{bmatrix} bb\\ba \end{bmatrix} \begin{bmatrix} aa\\aab \end{bmatrix} \begin{bmatrix} abb\\b \end{bmatrix}$$

The initial problem seems unsolvable. My argumentation is, that the solution can't end on $b$, because in the upper row no string ends on $b$. Thus, the solution has to end with an $a$ and only $\begin{bmatrix} ba\\baa \end{bmatrix} \begin{bmatrix} aba\\a \end{bmatrix}$ are left. I have been trying to continue on this argumentation for quite some time now, but could not end up with a logic explanation. Is this approach even correct or am I completely off track?

Answer 1

Let $x,y,z$ be the number of times that we use the first, second and third pair, respectively. Equating the number of $b$s we get $$y+z=x+y$$ and hence $$x=z$$ Therefore, the number of times the first pair is used in a solution must be equal to the number of times the third pair is used.

Let me call the three given pairs $p_1,p_2,p_3$, respectively. Note that any occurrence of a $p_1$ cannot followed by a $p_2$, a $p_1$, or be the last pair. This is because in the top string a $b$ is always followed by an $a$, while any of these cases would produce in the bottom string either two consecutive $b$s or a $b$ that is the last character. Therefore the occurrences of $p_1$ and $p_3$ in a solution must appear as the patter $p_1p_3$.

Finally, note that the last four pairs of a solution must be $p_3\mathbf{p_3}p_1p_3$. This cannot be since we computed that the number of $p_1$ pairs must be the same as the number of $p_3$ pairs and the third to last pair is a $p_3$ that is not preceded by a $p_1$.

---

To show that a solution must end with $p_3p_3p_1p_3$ we look at the top and bottom strings that get formed. You saw that $p_1$ cannot be the last pair used. Likewise $p_2$ cannot be the last pair, since the second to last character in the top would be $b$, while it would be $a$ for the bottom string. Using $p_3$ as last pair we have $$\begin{array}{r}\color{red}{aba}\\\color{red}{a}\end{array}$$ We need a $b$ as second to last character for the bottom string. So, we use $p_1$ as second to last pair. We get $$\begin{array}{r}\color{green}{aa}\color{red}{aba}\\\color{green}{b}\color{red}{a}\end{array}$$ Now we need an $a$ for the bottom string. If we use $p_2$ we would get a $b$ as a fifth to last character in the bottom string, but the top string has an $a$ in that position. Therefore, the third to last pair must be $p_3$. We get $$\begin{array}{r}\color{red}{aba}\color{green}{aa}\color{red}{aba}\\\color{red}{a}\color{green}{b}\color{red}{a}\end{array}$$ Once again we cannot use $p_2$ to provide the $a$ that is needed next in the bottom string, since it would give a $b$ in the sixth to last character in the bottom. However, the top string has an $a$ in that position. Therefore, we are forced to use another $p_3$. So, we got the ending $p_3p_3p_1p_3$.