Note: If you can find a proof of this, please give me just a hint first, so I can try to solve it on my own.
Let $\Sigma$ be a finite alphabet (set of symbols) and $s,t\in\Sigma^\ast$ two strings (sequences of symbols) of equal length $n$ over $\Sigma$. We denote by $s_i\in \Sigma$ the $i$-th symbol of $s$, and by $as\in\Sigma^{n+1}$ the concatenation of the symbol $a\in\Sigma$ with $s\in\Sigma^n$. First, define a reversal operation $\text{r}(i,j)$ on $s$ as the operation:
$$s=s_1...s_n\quad\mapsto\quad s_1...s_{i-1}\ \ s_j s_{j-1}...s_{i+1}s_i\ \ s_{j+1}...s_n$$
that extracts the substring $s_i\dots s_j$ from $s$, reverses it, and puts it back in the same place, where $1 \le i\le j \le n$. Then, define the reversal distance $d_r(s,t)$ between $s$ and $t$ as the minimum number of reversal operations (on either $s$ or $t$) needed to transform $s$ into $t$ ($d_r(s,t):=\infty$ if not possible).
Conjecture: Let $a\in\Sigma$ and $s,t\in\Sigma^n$. Prove (or find a counterexample) that:
$$d_r(as,at)=d_r(s,t)$$
(In other terms, we can disregard the longest common prefix between two given strings when transforming one into the other.) Note that $a$ can occur in $s,t$.
Example: $a=1,\ s=23141,\ t=41123$
$$ \begin{array}{cl|cl} as\to^2 at & & s\to^2 t & \\ \hline \underline{1\ 23}141 & \text{r}(1,3)\ & \underline{2314}1 & \text{r}(1,4)\ \\ \underline{3\ 21141} & \text{r}(1,6)\ & 41\underline{321} & \text{r}(3,5)\ \\ 1\ 41123 & & 41123 & \\ \hline \end{array} $$
A few remarks:
- That $d_r(as,at)\le d_r(s,t)$ is obvious, the converse less so.
- If $n\gt 0$ and $d_r(as,at)=1$ then $d_r(s,t)=1$.
If $n\gt 0$ and $a$ does not occur in $s,t$, then it must return at the initial position at some point. Therefore, the same reversal operations that transform $as$ into $at$ can be easily adjusted to transform $s$ into $t$, so that the relative positions between all the other symbols excluding $a$ remain the same. This implies the conjecture in this case.
Induction alone doesn't seem to be powerful enough. Also, most results I've found in the literature either provide lower/upper bounds on the minimum $k$, or concern the computational complexity of this kind of problems, collectively known as sorting by reversals.
- I tested it via computer on random instances up to a reasonably high $n$ and it seems to hold.
I've edited this question numerous times, mainly to consider some variation of the conjecture. We write $s\to^k t$ if $s$ can be transformed into $t$ by application of exactly $k$ reversals:
Assume $i\lt j$ (i.e. $\text{r}(i,i)$ are disallowed). Prove that if $as\to^k at$ then $s\to^k t$. Counterexample: $$ \begin{array}{cl|cl} as\to^1 at & & s\to^1 t & \\ \hline \underline{1\ 1}23123... & \text{r}(1,2)\ & 123123... & ? \ \\ 1\ 123123... & & 123123... & \\ \hline \end{array} $$
Assume $i\lt j$ (i.e. $\text{r}(i,i)$ are disallowed). Prove that if $as\to^k at$ and $s\neq t$ then $s\to^k t$. Counterexample: $$ \begin{array}{cl|cl} as\to^3 at & & s\to^3 t & \\ \hline \underline{1\ 23}4 & \text{r}(1,3)\ & 234 & ? \ \\ 3\ 2\underline{14} & \text{r}(3,4)\ & & ? \ \\ \underline{3\ 241} & \text{r}(1,4)\ & & ? \ \\ 1\ 423 & & 423 & \\ \hline \end{array} $$
For sake of completeness, the original conjecture above can be practically re-written as: Prove that if $n\gt 0$ and $as\to^k at$ then $s\to^k t$.
Edit: Possible counterexample to the original conjecture:
$$
\begin{array}{cl|cl}
as\to^3 at & & s\to^3 t & \\ \hline
\underline{4\ 221}31441 & \text{r}(1,4)\ & 22131441 & ? \ \\
1\ 2\underline{2431441} & \text{r}(3,9)\ & & ? \ \\
\underline{1\ 2144}1342 & \text{r}(1,5)\ & & ? \ \\
4\ 41211342 & & 41211342 & \\ \hline
\end{array}
$$