Very nice! The trick is to realize that a string $\left(b_1, b_2, ..., b_n\right)$ can be reached from a string $\left(a_1, a_2, ..., a_n\right)$ if and only if we can find a 213-avoiding permutation $\sigma \in S_n$ such that every $i \in \left\{1, 2, ..., n\right\}$ satisfies $b_i = a_{\sigma\left(i\right)}$. (Recall that a permutation $\sigma$ is said to be 213-avoiding if there exist no $a < b < c$ satisfying $\sigma\left(b\right) < \sigma\left(a\right) < \sigma\left(c\right)$.) All that remains then is to show that the inverse of a 213-avoiding permutation is 213-avoiding; and this is clear. OK, this is not a full solution but the details are straightforward.

We can also induct for this question. The base case is clear. Suppose it is true for strings of length $k$, we will prove for $k+1$. From the condition we only need to show that if $A$ reaches $B$, then $B$ reaches $A$ Assume WLOG that string $A$ is ($1,2...,k+1$), which goes to $B$ ($a_1,a_2...a_{k+1}$) after inserting arrows. Now let $k+1$ go to position $a_i$, so $a_1,a_2,...a_{i-1}$ must be in ascending order, note that if we remove $k+1$ from $A$ (and the arrows before), we will get ($a_1,a_2...a_{i-1},a_{i+1},...a_{k+1}$) instead, which can be jumbled back to $1,2,...k$ from induction by putting arrows in some config $C$. Further in cofig $C$ there will not be arrows between $a_1,a_2,...a_{i-1}$, since they are in ascending order and the final config is also numbers in ascending order. Now add arrows as follow: For ($a_1,a_2...a_{i-1},a_{i+1},...a_{k+1}$), put the arrows as in config $C$, then add in $a_i$ such that there are no arrows before, and put an extra arrow plus the arrows that were between $a_{i-1}$ and $a_{i+1}$ between $a_i$ and $a_{i+1}$. It is clear that the ending result will be ($1,2,...,k+1$), and we are done from induction. More details for final part: Let's say if we do the operations according to arrows of config $C$ in ($a_1,a_2...a_{i-1},a_{i+1},...a_{k+1}$) up to the arrows before $a_{i+1}$, then we get $(a_1,a_2,...,a_{i-1},c_{i+1}a_{i+1},...c_{k+1}a_{k+1}$ where $c_j$ is number of arrows before $a_j$, then after that we continue with the remaining operations to get ($1,2,....k$). Now after inserting $a_i$, we also do operations up to before $a_{i+1}$, then we will have $(a_1,...,a_{i-1}, k+1,(c_{i+1}+1)a_{i+1},c_{i+2}a_{i+2},...,c_{k+1}a_{k+1})$. Now we use the extra arrow that was inserted to get to $(a_1,...,a_{i-1},c_{i+1}a_{i+1},c_{i+2}a_{i+2},...,c_{k+1}a_{k+1},k+1)$, if we continue now we will then get $(1,2,...,k+1)$

First, define the original string as the sequence of letters without the left arrows and the resulting string as the string that is typed with the left arrows. In addition, define the input string as the string with both the letters and the left arrows. In the example, the original string would be "abcdef", the resulting string would be "faecdb", and the input string would be "ab$\leftarrow$cd$\leftarrow\leftarrow$e$\leftarrow\leftarrow$f". We define a construction that takes the resulting string back to the original. First, assume that is for any prefix of the input string, the number of left arrows is no more than the number of letters. With such a string, we can add left arrows to the end of the input string until there are an equal number of letters and arrows. Now, we replace each arrow with a capital letter in the following manner: Traverse the input string from left to right. For each left arrow encountered, replace the left arrow with the first unmatched letter to its left. Under this transformation, the input string in the example would become "abBcdDCeEAfF". Note that the subsequence of capital letters forms the reverse of the resulting string. Consider the operation of reversing the transformed input string, and replacing all lowercase letters with left arrows. By symmetry, we get a new input string with the roles of the original and resulting strings swapped. In the example, the new input string would be "F$\leftarrow$AE$\leftarrow$CD$\leftarrow\leftarrow$B$\leftarrow\leftarrow$". What we are essentially doing is viewing the input string as a string of balanced parentheses. The opening parentheses form our original string, and the closing parentheses form the resulting string.

^ My solution on the actual test was exactly the same as Draco's, so I wanted to add some motivation (at least, this is how I personally was motivated to find this solution). I recommend you read Draco's solution before reading this. The condition you are asked to prove implies two main solution routes: finding a condition for reachability (like in Darij's solution) or constructing an explicit algorithm to recreate the original string after it was changed into another string. Both clearly immediately imply the desired result. Since an algorithm would imply the result, and since the question seems somewhat algorithmic in nature, such an algorithm probably exists. Since you are "reversing" a process, you might want to look at something like reading the string from right to left or replacing arrows with letters and vice-versa. After keeping this in mind and doing some small examples with 4 or 5 letter words, the desired algorithm quickly becomes apparent. This was by far my favorite problem on the exam... it was quite interesting, not completely trivial, and seems like a problem that even a non-mathematically-oriented person could possibly solve if given enough time, and with enough creativity. Moreover the two solution routes I described both yield results stronger than the question itself and give real insight into the inner workings of the problem.

Since I really like this problem, I'll add a couple of my own comments too. My motivation was based on noticing the similarity of this problem to tree traversals. We can view typing a letter as going to a child labeled with that letter, and typing a left arrow as going up to the parent of the current vertex. When we look at the Euler tour representation of such a tree, we obtain the solution above.

Nice problem! I find it really hard to phrase my solution in words. Sorry if it is vaguely written. Also, sorry for an overlong solution... I honestly can't figure out how to make the following shorter.

Sketch of my proof. Let $A=\overline{a_1a_2\ldots a_n}$ and $B=\overline{b_1b_2\ldots b_n}$ be two words such that $B$ is reachable from $A$. We will prove the inverse. We say for $i<j$ that $a_j$ precedes $a_i$ in $B$ if $a_i=b_k$, $a_j=b_l$ and $l<k$. Lemma: Let $A$ and $B$ be as above. Assume that $a_j$ precedes $a_i$ in $B$. Then $a_{j+1},a_{j+2},\ldots a_{n}$ all precede $a_{i}$ in $B$. Proof: I think the proof is quite strightforward it holds due to the fact we can't use ''$\rightarrow$''. For $b_i=a_{i'}$ let $\lambda (b_i)$ denote number of letters $b_j$ ($j<i$) such that $b_j=a_{j'}$ and $j'>i'$ and $\Lambda=\sum _{i=1}^n\lambda (b_i)$. Now we'll present an algorithm that transform $B$ to $A$ using "$\leftarrow$". We go from $i=1$ to $i=n$. If for particular $i$, $\lambda(b _i)>0$ we put before $b_i$ "$\leftarrow$" until $\lambda (b_i)=0$ (it's obvious that $\lambda (b_i)=0$ is possible to be obtained). This operation decreases $\Lambda$ and at the end there should $\lambda (b_i)=0$ for every $i$, so $\Lambda = 0$ and it is clear that we get $A$. Therefore $A$ is reachable from $B$.

The 213 characterization is very strong, but we only need a particular case of it for this solution. It clearly suffices to prove one implication. Furthermore, since the exact letters are irrelevant, we will prove by induction on $n$ that $S = 12345 \dots n$ is reachable from a permutation $\sigma$ if $\sigma$ is reachable from $S$. Base case: $1$ is reachable from $1$. Inductive step: Suppose the result is true for $n-1$. Now suppose $\sigma$ is reachable from $S = 123\dots n$. Define $k$ such that $\sigma(k) = n$. Lemma. $\sigma(1) < \sigma(2) < \dots < \sigma(k) = n$. Proof. Suppose $\sigma(i+1) < \sigma(i)$ for some $1 \le i \le k-1$. Now consider typing $i$. Because $i+1$ is to the left of $i$, we must use the $\leftarrow$ key to place the cursor to the left of $i$. However, once the cursor is to the left of $i$, it must remain to the left of $i$ since there is no $\rightarrow$ key. Therefore, $k$ must be to the left of $i$ as well, contradiction. Let $S'$ and $\sigma'$ be obtained from $S$ and $\sigma$ respectively after removing $n$. By removing the last step from the process to reach $\sigma$ from $S$, we obtain a process to reach $\sigma'$ from $S'$. By the inductive hypothesis, we can reach $S'$ from $\sigma'$. By the Lemma, the cursor will be at the rightmost position after typing $\sigma(k-1)$ (since using $\leftarrow$ will immediately put $j$ before $i$ when in fact $i$ should be after $j$ due to $i < j$), so we can type $\sigma(k) = n$. Then use $\leftarrow$ and continue with the process of reaching $S'$ from $\sigma'$. Thus, $S$ is reachable from $\sigma$, completing the inductive step and thus the proof.

It suffices to show that if we can get $B$ from $A$, then we can get $A$ from $B$. Firstly, assume the elements of $A$ are all distinct; we can do this by simply renaming $A$ as $123\cdots n$. Then $B$ is some permutation of $[n]$. Call $A$, the identity permutation $id$ and call $B$ as $\pi$. We want to show that if we can get from $id$ to $\pi$ then we can get from $\pi$ to $id$. Call the elements of $\pi$ as $\pi(1), \pi(2), \ldots, \pi(n)$. We induct on the number of characters of $\pi$ we have written down so far, call this $k$. The inductive hypothesis is that we have written down the first $k$ elements of $\pi$ such that they are in increasing order. Call the current set of numbers $\sigma$. Suppose the cursor is right after some position $\ell$ in $\sigma$. We want to show that $\pi(k+1) < \sigma(\ell+1)$ to finish the induction step. (Because we can only go $\leftarrow$, not $\rightarrow$.) We know $\sigma(1)<\cdots \sigma(\ell)< \sigma(\ell+1)< \cdots < \sigma(k)$. (If $\ell=k$ then we are good; just write down $\pi(k+1)$. So suppose $\ell \le k-1$. Let $\sigma(\ell+1) = \sigma(\ell)$.) Case 1: $\pi(k+1) < \sigma(\ell)$. Then simply backtrack till the point where we need to write $\pi(k+1)$, so we would stop the cursor, $\ell$, when we first get $\pi(k+1) < \sigma(\ell+1)$. Case 2: $\sigma(\ell) < \pi(k+1) < \sigma(\ell+1)$. Then simply write down $\pi(k+1)$. It is supposed to be ahead of $\sigma(1),\ldots,\sigma(\ell)$ in $id$, and indeed when we write it down it appears ahead of $\sigma(\ell)$. Case 3: $\pi(k+1) > \sigma(\ell+1)$. We want to show that this case is impossible, i.e. we must have $\pi(k+1) < \sigma(\ell+1)$ (can't be equal since we already have written down $\pi(k+1)$, but not $\sigma(\ell+1)$). We will have to now invoke the fact that we were able to go from $id$ to $\pi$ with the process. Suppose $\pi(k+1) > \sigma(\ell+1)$. Then the cursor is at a point where the number we are about to write down is more than $\sigma(\ell+1)$. This means that $\sigma(\ell)$ was ahead of $\sigma(\ell+1), \sigma(\ell+2), \ldots, \sigma(k)$ in $\pi$, since we had to backtrack ``too much''. But since $\sigma(k) > \sigma(\ell)$, this means we must have written down $\sigma(\ell)$ and then backtracked at least once. But now, we have a larger number before a smaller number, whereas we are trying to get the identity permutation. So this case is impossible. This completes the inductive step. Therefore, at the end of the process, we must have $\pi$ sorted such that all $n$ elements are in increasing orde. But this is just $id$, so we are done. $\blacksquare$ Here's an example to show what's going on in the proof a bit more clearly. Suppose $n=6$, so $id = 123456$. Suppose $\pi=346521$, which can be reached as follows: \[ 1| \to |1 \to 2|1 \to |21 \to 3|21 \to 34|21 \to 345|21 \to 34|521 \to 346|521. \]Now, the process to get back is as follows: \begin{align*} 3| &\to 34| \to 346| \to 34|6 \to 345|634|56 \to 3|456 \\ &\to |3456 \to 2|3456 \to |23456 \to 1|23456. \end{align*}The $(k,\ell)$ values at each step in the process are as follows: \[ \begin{array}{ccccccc} 3| &\to \qquad 34| &\to \qquad 346| &\to \qquad 34|6 &\to \qquad 345|6 &\to \qquad 34|56 &\to \qquad 3|456 \to \cdots\\ k=1 &\qquad k=2 &\qquad k=3 &\qquad k=3 &\qquad k=4 &\qquad k=4 &\qquad k=4 \\ \ell = 1 &\qquad \ell=2 &\qquad \ell=3 &\qquad \ell=2 &\qquad \ell=3 &\qquad\ell=3 &\qquad \ell=2 \end{array} \]

My solution seems too easy for a TSTST problem, so I hope I am not missing something numbertheorist17 wrote: Let $\leftarrow$ denote the left arrow key on a standard keyboard. If one opens a text editor and types the keys "ab$\leftarrow$ cd $\leftarrow \leftarrow$ e $\leftarrow \leftarrow$ f", the result is "faecdb". We say that a string $B$ is reachable from a string $A$ if it is possible to insert some amount of $\leftarrow$'s in $A$, such that typing the resulting characters produces $B$. So, our example shows that "faecdb" is reachable from "abcdef". Prove that for any two strings $A$ and $B$, $A$ is reachable from $B$ if and only if $B$ is reachable from $A$. Denote $A=a_1a_2 \dots a_n$ and $B=b_1b_2 \dots b_n,$ such that $B$ is reachable from $A$. We prove the result by induction on $n \geq 1$. The result is obvious for $n=1,2$. Suppose the result is true for $n-1$. We will show that it is true for $n$ as well. Assume $b_k=a_n$ for some $k \in [n]$. Let $A'=a_1a_2 \dots a_{n-1}$ and $B'=b_1b_2 \dots b_{k-1}b_{k+1} \dots b_n$. Since $B$ is reachable from $A$, so simply removing $a_n$ and the left arrows after $a_{n-1}$,we get that $B'$ is also reachable from $A'$. By the induction hypothesis, we can say that $A'$ must be reachable from $B'$. Now, consider the sequence of arrows inside $B'$ so that we reach $A'$. To this sequence, concatenate the string {$b_k \leftarrow$} just after $b_{k-1}$ (If $k=1$, then simply concatenate this string at the beginning of the sequence). Note that this new string constitutes a sequence of arrows inside $B$. Also, due to the addition of an extra left arrow after $b_k$, the whole sequence after $b_k$ (i.e. starting from $b_{k+1}$) will simply add in after $b_{k-1}$ according to the order of left arrows specified in $B'$. Thus, the string which evaluates by this sequence of arrows is simply the "result" of $B'$ (that is $A'$ in this case), with $b_k$ added at the end. Since $b_k=a_n$, and $A'+a_n=A$, so we get that this new string is nothing but $A$. Thus, we have created a sequence of arrows taking $B$ to $A$, as desired. Hence, done. $\blacksquare$

I hope this works... I think I cleared up all of the minor details for this approach (which are in abundance), but it's totally possible that there are more. Thanks to hliu1 and Whee, the former for helping clear up too many details The latter just read. The proof itself is not as concrete as I would like for it to be (and is also a little unorganized), but I think it works... We show that if $B$ is reachable from $A$, then $A$ is reachable from $B$. We know that if this statement holds, then so does its analogous converse. We give a somewhat algorithmic-induction on the number of characters. The characters used are irrelevant, so we just use $abcd...$ in place of a $n$-letter string. The base case is trivial, since $a$ is obviously reachable from $a$. We assume that $A_0=\underbrace{abcd...}_{n \text{ letters}}$ is reachable from $B_0$, and show that $A_1=abcd...\beta$ is reachable from $B_1$ with $n+1$ letters as well. Further, we assume that $B_1$ is reachable from $A_1$. Note that $B_1$ is $B_0$ but with the letter $\beta$ inserted somewhere, after the first $i$ letters. Revert the typing of $A_0$ until only $i$ characters from $B_0$ have been used. That is, the next letter to be used in the typing of $A_1$ is $\beta$. $\phantom{.}$ Claim: The letters before and including $\beta$ in $B_1$ must be lexicographically increasing. Proof: The case with no left-arrows in the construction of $B_1$ is trivial. Suppose that one exists, and assume what we have already typed during the construction of $B_1$ is in lexicographically increasing order. Then after we left-arrow, we will only type larger characters compared to before ($A_1$ is sorted). Repeating this claim inductively yields the result. $\phantom{.}$ Type $\beta$, which is the last letter of $A_1$. We can do this because, by our previous claim, the cursor will be at the rightmost position after typing the letters before $\beta$. Now use the left arrow until the cursor is right after the letter before $\beta$ in $B_1$. From here, proceed as we would in the typing of $A_0$ using $B_0$, and we can do this since $\beta$ is the last character in $A_1$. We're done. $\blacksquare$

bad write-up

For any two string $A$ and $B$, we must obviously have $A$ and $B$ with the same multiset of characters. Assume that $B$ is reachable from $A$. Then we wish to show that $A$ is reachable from $B$. Let $A_n = 12345\dotsm n$ and $b_n =\sigma(1)\sigma(2)\sigma(3)\dotsm\sigma(n) .$ Claim: There can be no indices $x < y < z$ such that $\sigma(y) < \sigma(x) < \sigma(z),$ called $213$-avoiding, in $B$. Proof: Clearly, this is needed. To prove it is sufficient, we write $B$ until we reach $k$. Now we can oly get stuck if $k+1$ is to the right, with a character in betwwen $k$ and $k+1.$ This gives a $213$ pattern. Claim: A permutation $\sigma$ of $\{1,2,\dots,n\}$ is $213$-avoiding if and only if its inverse permutation $\sigma^{-1}$ is as well. Proof: Suppose we have $x<y<z$ and $\sigma(y)<\sigma(x)<\sigma(z).$ Then we must also have $\sigma^{-1}(\sigma(x))<\sigma^{-1}(\sigma(y))<\sigma^{-1}(\sigma(z)).$ $\blacksquare$ By using the typing algorithm that results in $A \rightarrow B,$ we arrive at a permutation that is $213$-avoiding by the claim. Then, by the second claim, $\sigma^{-1}$ is $213$-avoiding, giving a way to do $B \rightarrow A.$ $\blacksquare$

WLOG, suppose that the starting string $A$ is $1234\ldots n$, and the string $B=b_1b_2\ldots b_n$ is some permutation of $A$. Denote by $\pi(a)$ the position of $a$ in $B$, for example if $B=1423$ then $\pi(1)=1$ and $\pi(4)=2$. Claim: $B$ is reachable from $A$ if and only if there do not exist $i<j<k$ with $\pi(j)<\pi(i)<\pi(k)$. Proof: If there exist such $i,j,k$, then after entering $i$ and $j$, one is clearly unable to enter $k$ to the right of $i$. Now suppose that $B$ cannot be reached from $A$, and let $a$ be the least number such that one is unable to write it in the correct spot in $B$. This implies that $a$ must be to the right of $a-1$, and that there must be some other (smaller) number between $a-1$ and $a$, which implies the existence of such an $i,j,k$. I will now show that if $B$ is reachable from $A$, then $A$ is reachable from $B$. Since $B$ is reachable from $A$, there cannot exist $i<j<k$ with $b_j<b_i<b_k$. Now suppose FTSOC that $A$ is not reachable from $B$, i.e. there exist $p,q,r$ with $p<q<r$ such that $b_q<b_p<b_r$. This implies that there exist $i,j,k$ with $i<j<k$ such that $\pi(j)<\pi(i)<\pi(k)$, namely $(i,j,k)=(b_q,b_p,b_r)$, since $\pi(b_a)=a$ for all $a$. But this is a contradiction, since it implies that $B$ is not reachable from $A$. Now suppose that $B$ is not reachable from $A$, and FTSOC suppose that $A$ is reachable from $B$. Using the above result, this implies that $B$ is reachable from $A$, which is a clear contradiction. $\blacksquare$

Hope this is right!! FTSOC, assume that $[1,2,...........,n]\rightarrow[a_1,a_2,.......,a_n]$ but $[a_1,a_2,.......,a_n] \not\rightarrow[1,2,...........,n]$ How do the arrows work?:- We start from the last $\leftarrow$ arrow and move towards right. If we have $\leftarrow y_1 y_2......y_n$ then the sign $\leftarrow$ applies to all the $y_i$'s however in this case we apply the arrows from left to right. Define $\omega(x):=$ The position of $x$ in $[a_1,a_2,.....,a_n]$ and define $\Omega(x):=$ the original position of $x$ in $[1,2,......,n]$ Call a term $a_{j_n}$ "bad" if $\omega(a_{j_n})>\Omega(a_{j_n})$ and "good" if $\omega(a_{i_n})>\Omega(a_{i_n})$ (The existence of $\omega(n)$ depends upon $[1,2,...........,n]\rightarrow[a_1,a_2,.......,a_n]$) Claim: If there are $>\left\lfloor \frac{n-1}{2} \right \rfloor$ 'good' or 'bad terms' two of them must be consecutive. Proof: This is an direct consequence of pigeon hole principle. Define $f(x)=\max_{1 \le x \le n,\max x_k}=k$ where $x_k$ is the number of $\leftarrow$s between two consecutive terms.(when we convert $[1,2,.......,n] \rightarrow [a_1,.......,a_n]$) Before we get to the main algorithm we discuss an important conditions which make our work simpler:- Condition for "good" numbers: There must exist solutions to the equation $$\omega(a_{j_{x}})-\Omega(a_{i_x})= \sum_{j=1}^{f(a_{i_x})}$$Proof: We'll show this inductively:For the base case $x=1$ we have $$\omega(a_{x_1})-\Omega(a_{x_1})=x_1$$which obviously has an solution. Assume that this works for $x=n$ and we will show that this works for $x=n+1$ However this is simple since $$\omega(a_{i_{n+1}})-\Omega(a_{i_{n+1}})=\sum_{k=1}^{f(a_{i_n})} x_k+\sum_{k=f(a_{i_n})}^{f(a_{i_{n+1}})} x_k>0$$which has a solution. Final algorithm: First we work on $1$ and shift it front. If we want to take any term left we add more $\leftarrow$s in front of it and we do this by condition 1. If we want to take any term backwards we would need $\sum_{k=1}^{f(a_m)} x_k>\sum_{k=f(a_m)}^{f(a_{m+1})} x_k$ and hence we place more $\leftarrow$s behind it such that between each $a_i$ such that the already established positions aren't disturbed and the given term also moves backward. By the algorithm we get $B \implies A$, implying the result.$\blacksquare$

Just notice that each left arrow fixes the position of another character and then we need to avoid a "213" triple as seen in #2 which is simple.

Without loss of generality, let string $A$ be $a_1a_2a_3\dots a_n.$ Let $\pi$ be a permutation of $[n]$ and let $B(\pi)$ be a string $a_{\pi(1)}a_{\pi(2)}\dots a_{\pi(n)}.$ In such a string, call a transposition in some string permutation $B(\pi)$ two characters $a_{\pi(i)}$ and $a_{\pi(j)}$ for which $i< j$ and $\pi(i) > \pi(j).$ We claim that string $B(\pi)$ is reachable from $A$ if and only if for each transposition, the value $\pi(i)$ is greater than every single index that follows in string $B(\pi).$ Clearly, this condition is reversible, so it suffices to prove our claim. $~$ To prove our claim, we first notice what happens when we do have a transposition for which $\pi(i)$ is less than $\pi(k)$ where $k> i.$ Note that when we place $a_{\pi(i)}$, we must go left before placing $a_{\pi(j)}$, but then we cannot place letters to the right of $a_{\pi(i)}$, so we cannot correctly place $a_{\pi(k)}.$ $~$ If there is no such transposition, then we can go through the string using the algorithm of placing characters by their position relative to what is already typed.

I'm curious about the difficulty of this problem, since the details are much more complex than I expected, but the solution path is quite straightforward and motivated Main Claim 1: In a permutation of the positive integers 1 through $n$, the statements "for all $1\leq i<n$, $i+1$ is either anywhere left of or immediately right of $i$" and "there is no rise of more than 1 between consecutive terms going right" are equivalent. We will first show that $i+1$ is either anywhere left of or immediately right of $i$ implies that there is no rise of more than 1. Suppose FTSOC that $k+m$ is immediately right of $k$ for $m\geq2.$ Then, $k+1$ must be left of $k$, since the immediately right spot is occupied. However, there is now no way for it to reach $k+m$ from now on, since we are only allowed to go right by 1 per step, so we cannot bypass $k$ anymore, contradiction. Then, we will show that no $\geq2$ rise implies $i+1$ is either left of or immediately to the right of $i$. Suppose FTSOC that $i+1$ is more than one right of $i$, so there are other numbers between $i$ and $i+1.$ Consider moving to the right starting from the position $i$. Each time, we can either make it lower or increase it by 1. However, at the start, we must decrease it, since we know that $i+1$ appears later and we can't occupy it yet. However, then if we want to get back to $i+1$, we must pass through $i$ again, since we are only allowed to go up 1 at a time, and we are now lower than $i$. However, we already had $i$, contradiction. WLOG that the $A$ is a list of positive integers from 1 to $n$ in that order. If $B$ is not some permutation of 1 through $n$, then clearly neither of $A$ and $B$ is reachable from the other. Thus, for the rest of the solution, assume that $B$ is a permutation of 1 through $n$. Note that $B$ is reachable from $A$ if and only if for all $1\leq i<n$, $i+1$ is either anywhere before or immediately after $i$ in $B$, since we can only go forward by at most one per thing typed, but we are allowed to go back however far we need. Interpreting it the other way, $A$ is reachable from $B$ if and only if for all $1\leq i<n$, the position, in $A$, of the $i+1$th number in $B$ is to the left of or immediately after the position, in $A$, of the $i$th number in $B$. Since $A$ is sorted in order, this is just saying that $B$ contains no rise of more than 1, so by Main Claim 1, we are done.

WLOG let $A$ be the string $1,2, \dots, N$. Inserting $\leftarrow$'s into $A$ results in a permutation $a_1, a_2, \dots, a_N$ of $A$. The key claim is that this permutation is nonreachable if and only if there exist $i < j < k$ for which $a_j < a_i < a_k$. Otherwise, the permutation is reachable. Proof left as an excercise to the reader. If there don't exist $i < j< k$ and $a_j < a_i < a_k$, there don't exist $a_i < a_j < a_k$ and $j < i < k$ either; in other words, if a permutation is reachable, its inverse is also reachable.

It is equivalent to consider all permutations of $[n]$ where an element of the permutation corresponds to a character on the keyboard. In particular, we have the following characterization: Claim. A permutation $\sigma$ is reachable from the identity if and only if $\sigma$ is 213-avoiding. Proof. If $\sigma$ is not 213-avoiding, then suppose there exist $b, a, c$ with $a<b<c$ in that order. But if $\sigma$ is reachable, $a, b, c$ must be typed in that order, which is impossible because we can't skip over $a$, contradiction. To see that all such $\sigma$ are reachable, note that valid $\sigma$ must have $\sigma(i) < \sigma(1)$ for all $i \geq k$ and $\sigma(i) \geq \sigma(1)$ for $i < k$ for some $k$. We may perform a strong induction as follows: type $1$, then type $2, 3, \dots, k$ with suitable left arrows in between to construct the right $k-1$ digits of the string using the inductive hypothesis. (This is possible because the right $k-1$ digits are 213-avoiding.) Then, left arrow $k$ times and type the left $n-k$ digits of the string, as needed. $\blacksquare$ Finally, observe that the inverse of any permutation is 213-avoiding if and only if that original permutation was 213-avoiding. This implies the result.

hopefully not a fakesolve We will show that if $A$ is reachable from $B$, then $B$ is reachable from $A$, which will imply the conclusion by symmetry. Suppose that $B$ has length $n$, and number its characters in order from $1$ to $n$. Then the characters of $A$ must be some permutation $\{c_1, c_2, \ldots, c_n\}$ of $\{1, 2, \ldots, n\}$. We use the following algorithm to type out each characters of $A$ $c_i$, in order from $c_1$ to $c_n$: If $i = 1$ or $c_i$ is greater than the value of the $c_j$ immediately to the left of the cursor, type out $c_i$ with no left arrows before it Otherwise, hit the left arrow until the cursor lies before the character $c_j$ already typed out with the smallest value such that $c_j > c_i$ For example, if $B = abcdef$ and $A = faecdb$, then we would type $f \leftarrow ae \leftarrow cd \leftarrow \leftarrow b$. Suppose that this algorithm failed; this implies that after typing out some character $c_i$, there is either some character $c_j$ to the left of it such that $c_j > c_i$ or some $c_k$ to the right of it such that $c_k < c_i$. The first case can never happen due to the second step of the algorithm, and if the second case were to occur, the first time it happened (i.e. smallest such $i$) we would need $k < i - 1 < i$ and $c_{i - 1} < c_k < c_i$. But this is impossible because if $a$ and $b$ are two characters such that $a < b$ and $b$ comes after $a$ in $A$, the only characters that can lie between them in $A$ must have values greater than $a$. In other words, the permutation $c$ must be 213-avoiding. So, the algorithm works, and we are done.