Interesting question regarding evolution of algorithm under certain conditions

Question

On a random string of six digits containing numbers of the set $S=\{1,2,3,4,5,6\}$, repeat the following operation:

If $k$ is the first number of the string, then reverse the order of first $k$ numbers of the string.

For example: $342561\rightarrow 243561\rightarrow 423561\rightarrow 532461\rightarrow 642351\rightarrow 153426$

Prove that any such string would terminate with $1$ at the first position.

Now on checking a few examples, I have made a few observations:

$1.$ The last digit of the string is an increasing monovariant.

$2.$ The first digit of string is always a different number unless the last digit changes. This means that until the last digit of the string change, no number that appeared in the first position in the string will ever repeat.

$3.$ When the last digit reaches its maximum value (which is $6$ here), the observation $2$ works the same but for th second last digit now instead of the last one.

Now the first observation can be explained by the fact that the last digit will only change when we would have $6$ in the first position and no number in the string is greater than $6$.

The third observation can be explained by the fact that when the last digit reaches the value of $6$, this value would never change as all the numbers are less than $6$. Thus, the observation $2$ would now work with the second last digit instead of the last digit since it would be the same as applying the algorithm to a string of length $5$ instead of $6$.

Now if I can prove observation $2$, then I can say that since no number occuring in the first position repeats, we would have either $6$ or $1$ in the first position sometime in atmost $6$ steps. If we obtain $6$ before $1$ in the first position, then $6$ would move to the last position. Similarily after $6$ have moved to the last position, we would either have $1$ or $5$ in the first position after atmost $5$ steps and so on.

This indicates that after some finite steps, the sequence is bound to have $1$ at the first position.

Now I need help to prove observation $2$. Please help.

THANKS

Answer 1

The idea is as follows:

6 can be the first digit in the sequence at most once. After that, it's permanently stuck as the last digit of the sequence.

5 can be the first digit in the sequence at most twice. After 5 is the first digit, it'll be the 5th digit and can only move downwards if 6 becomes the 1st digit. But that can only happen once.

In general, $6 - n$ can be the first digit at most $2^n$ times. For after each time $6-n$ is the first digit, it only be dislodged from its position by a higher number; this dislodging can occur at most $\sum\limits_{i = 0}^{n - 1} 2^i = 2^n - 1$ times. You can use well-founded induction to make this argument rigorous.

Thus, the process will eventually terminate with 1.

Answer 2

Let us consider a generalized version of this problem where we are given some permutation $\pi$ of $[1, n]$ and let $f$ denote the function mapping such a permutation to the one resulting by applying the given operation. Further, we will call $\pi$ correct for $k$ if $\pi(k) = k$.

We begin by observing 2 properties of $f$:

1. $f$ preserves the correctness of a permutation $\pi$ at $k$ if $\pi(1) < k$, i.e. reversing the order of the first $\ell < k$ elements of the permutation does not change the position of $k$.
2. $f(\pi)$ is correct for $\pi(1)$, i.e. $f(\pi)$ is correct for the first element of $\pi$.

A simple corollary of these properties is that if $\pi$ is correct at $k$ and $f(\pi)$ is not then $f(\pi)$ must be correct for some $j > k$ on which $\pi$ is not correct. This follows from the fact that $k$ can only be moved to an incorrect position if the first element of $\pi$ is some $j > k$.

Now consider the following energy function $E$: $$ E \colon S_{[1, n]} \to \mathbb R, \pi \mapsto \sum_{\pi \text{ correct for } k} 2^{k} $$ Using the properties of $f$ established above we find that $E(f(\pi)) \geq E(\pi)$ with the inequality being strict exactly for all $\pi$ on which $f$ is not stationary.

As $S_{[1, n]}$ is finite, it follows that the state $f^m(\pi)$ of the algorithm (started on some initial permutation $\pi$) attains a maximal energy value after $p \leq |S_{[1, n]}| < \infty$ steps. We conclude that $f^p(\pi)$ must hence be a stationary point of $f$ which is equivalent to $f^p(\pi)$ being correct for 1.