3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Can you define what the input is and what the output should be? $\endgroup$
    – nir shahar
    Jun 28 at 17:16
  • 1
    $\begingroup$ For those who are unfamiliar with Post's correspondence problem $\endgroup$
    – nir shahar
    Jun 28 at 17:16
  • 2
    $\begingroup$ Ling Zhao's solver states that your instance is unsolvable, but doesn't explain why. You can try digging into the code to see how it came to this conclusion. $\endgroup$ Jun 28 at 22:27
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @j_random_hacker Clarified that point and from the linear algebra part kept only the part that was really needed for the argument. $\endgroup$
    – Urtur
    Jun 30 at 13:10

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.