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.

------------------------------------

The second option is somehow losing information...
Let's try experiments.

1 2 3
(nope, when it is sorted, it is game over)
('a': x y => y+1 x, 'b': x y  => x-1 x)

3 2 1
 a
3 3 1
   b
3 3 2
   a
3 3 3

Is there a longer process?
3 2 1
 a
3 3 1
   a
3 2 3
 a
3 3 3

It looks like that the number of positions in which a step can
be made is non-increasing. Can we prove it?

u  v > x  y
     a
u  x+1 v  y

Since v > x, it cannot be true that x+1 > v, so a move cannot be done
at the same position.
Questions:
(1) If u > x+1, can we tell that u > v?
(2) If v > y, can we tell that x > y?
Answers:
(1) Does not seem so: 5 5 2 1 => 5 3 5 1
(2) Also not: 5 5 1 1 => 5 2 5 1
OK, so the number of position in which a step can be made
is not necessarily decreasing, the
5 5 1 1 => 5 2 5 1 is a counterexample.

But somehow, the large number anyway traveled to the right.
I want some dicreasing semi-variant.

What about the sum of all the differences x-y
  for all the x > y and x being on the left of y.
* this is motivated by the fact that we are making almost
  "sorting swaps" which reduce the number of inversions in the permutation

However, the 'b' operation does not have to comply.
100 1 1 1 => 99 100 1 1

So what is the problem (for infinite process)?
100  1   1  1
 99 100  1  1
 99  2  100 1

Could we ever increase the first number again?
If applied to the first two numbers:
* The operation 'b' decreases the first number.
* The operation 'a' does not increase it.

So simply alphabetical order?
* The operation 'b' decreases the first of the two numbers
  => smaller lexicographical sequence
* Operation 'a':
  (1) x > y+1 => x changes to a smaller number y+1
      => smaller lexicographical sequence
  (2) x = y+1
      y+1 y => y+1 y+1
      => bigger lexicographical sequence
It does not work,
* of course, we had this in our experiments: 3 2 1 => 3 3 1

For contradiction, assume there is an infinite process.
* So the first number will be fixed since certain moment.
* If we do not perform an action on the first two numbers infinitely many times,
  there must be infinitely many actions 'a' on them, where
  y = x-1: x x-1 => x x
  (x is fixed thorough the process)
* So when focusing on the rest of the sequence, it looks like
  the same process on one less numbers
  except the first number can be raised from x-1 to x.
* So the first number (in the reduced sequence) is altering
  between x and x-1 (infinitely many times)

Let's return to the 100 1 1 1 example, and allow 99->100 at the first position.

100  1   1   1
 99 100  1   1
 99  2  100  1
100  2  100  1
100  99 100  1
 99 100 100  1
100 100  2  100

Somehow, the small numbers are useless because they just bubble to the left
and then I have to destroy them.

So, what exactly can happen on the second position, if the first one is
constantly 100? (and I use the first position infinitely many times)
* There is always 100 or 99 on the second position.
* So the allowed moves at the 2-3 positions are
  100 > x ==(b)==>  99 100
  100  99 ==(a)==> 100 100
  100  98 ==(a)==>  99 100
   99  98 ==(a)==>  99  99
* That means that (let's call the positions p1, p2, p3, ...)
  * I can put 100 to p3, if there was something less than 100
    (I get 100 to p2, and then apply (b))
  * Sometimes, I can raise 98 => 99 on p3.

The first of the two possible operations on p2,p3 is systematic and
  stronger than the 99 => 100 on p2.
So, let's have an analogous system, in which I can raise anything
  less than 100 to 100 on p1.

Why cannot I get a loop just on two positions?

2 1
1 2
100  2
 3  100 /  99 100
100 100 / 100 100
For some reason, I got the number 100 also to p2.

.....

Observation: The operations never decrease the total sum.
* op (a) increase the total sum
* op (b) increase it, or keep it the same, if it is
  (x, x-1) => (x-1, x)

So, if I want to keep the sum of all numbers fixed,
  I can use only the operation x x-1 => x-1 x
  * This cannot be done for infinitely many steps,
    since it is a "sorting swap"
    (the number of inverses decreases)

Therefore, in an infinite process, the overall sum
  have to exceed all bounds.
On the other hand, the first number is bounded...
Actually, if the maximum number is M, can we get by an operation
  anything bigger than M?
  * Well, no. Because M+1 would appear only if M was on
    the y position, meaning there was something bigger than M before.

Problem solved!

(1) The maximum number never increases. (making a bound on the sum)
(2) The sum never decreases.
(3) If the sum stays the same, only a sorting swap is performed.