Dgdrxrt

The following is a question from the IMO 2012 shortlist:

Several positive integers are written in a row. Iteratively, Alice chooses two adjacent
numbers $x$ and $y$ such that $x > y$ and $x$ is to the left of $y$, and replaces the pair $(x, y)$ by either
$(y + 1, x)$ or $(x − 1, x)$. Prove that she can perform only finitely many such iterations.

In a solution to this in page number 19, solution 3 in this document:

https://www.imo-official.org/problems/IMO2012SL.pdf

It is stated that score sequences for the given sequence do not repeat. Why is that so?

Solution 3. Let the current numbers be $a_1, a_2, ldots , a_n$. Define the score $s_i$ of $a_i$ as the number of $a_j$’s that are less than $a_i$. Call the sequence $s_1, s_2,ldots , s_n$ the score sequence of $a_1, a_2, ldots, a_n$.
Let us say that a sequence $x_1,ldots , x_n$ dominates a sequence $y_1,ldots , y_n$ if the first index $i$ with $x_i neq y_i$ is such that $x_i < y_i$. We show that after each operation the new score sequence dominates the old one. Score sequences do not repeat, and there are finitely many possibilities for them, no more than $(n − 1)n$. Hence the process will terminate.

Consider an operation that replaces $(x, y)$ by $(a, x)$, with $a = y + 1$ or $a = x − 1$. Suppose that $x$ was originally at position $i$. For each $j < i$ the score $s_j$ does not increase with the change because $y ≤ a$ and $x ≤ x$. If $s_j$ decreases for some $j < i$ then the new score sequence
dominates the old one. Assume that $s_j$ stays the same for all $j < i$ and consider $s_i$. Since $x > y$ and $y ≤ a ≤ x$, we see that $s_i$ decreases by at least $1$. This concludes the proof.

Domination as described is a transitive, non-reflexive property. Transitive means that if you have a chain $S_1prec S_2prec S_3preccdotsprec S_k$ of sequences $S_i$, each one dominating the one before it (I just decided that $prec$ would be a nice symbol to use for domination), then any sequence dominates all sequences before it in the chain, not just the one immidiately preceeding it. Non-reflexive means that no sequence dominates itself.

Put these two properties together, and you see that no sequence can appear twice in the chain. Of course, the transitive and non-reflexive properties mut be proven (transitive is usually described and proven using only a chain of length 3, and together with some almost trivial induction, that's enough to get what I described above). You also need to prove that whatever Alice does, she will produce such a chain, and that's what the second paragraph of the given solution focuses on.