Does perfect knowledge help you prevent a subword in a word?

Question

Let there be three words $S_1, S_2,$ and $S_3$ using letters $A$ and $B$ such that neither $S_1$ nor $S_2$ has $S_3$ as a substring. For given $S_3,$ if there is a function that takes $S_1$ and $S_2$ as inputs and outputs an $S_4$ such that $S_1 S_4 S_2$ doesn't contain $S_3,$ is this guaranteed to be achievable by a constant function?

Answer 1

Yes, this is possible.

Construction

Let $f(S_3, S_1, S_2)$ denote the function that we assume exists. Choose some fixed $S_3$ and let $N = |S_3|$. Denote the letters in $S_3$ by $p_k$, $1 \le k \le N$. Define the "opposite" function $o$ by $o(A) = B$ and $o(B) = A$.

Let $T_1$ be the string consisting of $N$ copies of $o(p_N)$. Let $T_2$ be the string consisting of $N$ copies of $o(p_1)$. Let $C = f(S_3, T_1, T_2)$. Then we can satisfy your requirements by choosing $S_4 = T_1 C T_2$.

Proof

Fix some $S_1$ and $S_2$ that don't have $S_3$ as a substring. We can use cases to check that $S_1 S_4 S_2$ also doesn't have $S_3$ as a substring.

1. Fully inside $S_1$: We can't find a copy of $S_3$ here by assumption on $S_1$.
2. Crossing the border from $S_1$ into $S_4$: Any substring of length $N$ that crosses the border will end inside $T_1$, so the last letter will be $o(p_N)$, so this substring can't be a copy of $S_3$.
3. Fully inside $S_4$: It's impossible to find a copy of $S_3$ here because of the way we chose $C = f(S_3, T_1, T_2)$.
4. Crossing the border from $S_4$ into $S_2$: Analogous to case (2) above. Any substring of length $N$ that crosses the border will start inside $T_2$, so the first letter will be $o(p_1)$, so this substring can't be a copy of $S_3$.
5. Fully inside $S_2$: We can't find a copy of $S_3$ here by assumption on $S_2$.