did you mean "only finitely" ?

roza2010 wrote: did you mean "only finitely" ? sorry; edited.

When I saw this problem last week, I was in doubt whether I had received the real shortlist! Everybody with the most basic training in invariants can do this.

Let there be $n$ numbers $x_1$ to $x_n$ where $x_1$ is at the right and $x_n$ at the left and let $f(x_i)= \frac{x_i}{2^i}$. Then after each move $\sum_{i=1}^{i=n} f(x_i)$ has been increased by at least $\frac{1}{2^n}$. Because the maximum of $\{x_1,\cdots, x_n\}=m$ doesn't increase. The total function valuesum can't be bigger than $2m$ and hence the game has to end somewhere. (after a number smaller than $m2^{n+1}$ the game has ended).

1. No move can change the maximum. 2. After finitiely many moves, all maximum values have accumulated at the right end of the row, and then a subgame starts with the remaining non-maximum values.

There was something nice about this problem in the shortlist, that with the following statement could have been a medium-difficult problem in IMO 2012: Show that considering only the number of positive integers, she can perform at most $n^{n-1}$ (i think, it has been written by Carlos di Fiore as a comment ). Show that this cant be better.

I don't understand the official Solution #2. What does reverse lexicographical order mean? If this means that the rightmost is $x_1$, then the 2nd to the rightmost is $x_2$, then the leftmost is $x_n$. After the operation is done, then if we consider the notation of being greater/less than, the resulting set would be less than the first set, not greater. For example, if we take the set (2014, 201, 14, 4), then we apply the operation to (201,14), we get (2014, 15, 201, 4) or (2014, 200, 201, 4). Then the reverse lexicographical order of the first set is (4, 14, 201, 2014), and the possible resulting sets are (4, 201, 15, 2014) or (4, 201, 200, 2014) Then since looking from the end, the first term that changed went down (201 to 15 or 201 to 200), the resulting set is less than the original set. Actually this cannot also continue forever, so this could also be used to solve the problem . What I do not understand is why does the resulting set become greater instead of becoming lesser, like my example above, where the set actually became lesser! Or maybe I actually misinterpreted the meaning of reverse lexicographical order or he meant that considering the lexicographical order means LOOKING from the end, not actually reversing the sequence and its terms.

You have the reverse part of "reverse lexicographical order" right, although it looks like you did it twice or something. Lexicographical order means that the comparison is done based on the first number that differs. For $(4, 14, 201, 2014)$ and $(4, 201, 15, 2014)$, the first place where these two differ is the second position with $14$ and $201$. $14 < 201$. Therefore, under lexicographical ordering, $(4, 14, 201, 2014) < (4, 201, 15, 2014)$.

Suppose the number of numbers written is $n.$ We use strong induction on $n,$ the base case $n=2$ being trivial. Suppose given any $j$ numbers, there can be only finitely many operations on them. Now append another number to the list. Let the numbers written be $a_1, a_2, \cdots , a_{j+1},$ and let $a_m = \max\{a_i\}.$ Note that $a_m$ never changes. Alice cannot operate on $a_{m-1}$ and $a_m$ since $a_m \geq a_{m-1}.$ Hence, she must operate on $a_m$ and $a_{m+1}$ or otherwise the desired result would follow by applying the inductive hypothesis on $a_1, a_2, \cdots , a_{m-1} , a_m$ and $a_{m+1}, \cdots , a_j.$ We then have $(a_m, a_{m+1}) \rightarrow (a_{m}-1, a_m).$ After applying finitely many operations of $a_m$ and the number just after it, we can send $a_m$ to the rightmost side after which no more operations are allowed. The result follows by the inductive hypothesis. $\blacksquare$

Another awesome monovariant is $a_1 + 2a_2 + 3a_3 + \dots + n a_n$, if we let the numbers be $a_1, a_2, \dots, a_n$ from left to right.

Suppose our list is $a_1, a_2, ..., a_n$, and take $A = \max\{a_i\}$. As noted above, $A$ doesn't change. Consider the quantity $Q = \sum_i |A-a_i|$. This is strictly decreasing unless we perform a move of the form (*) $(x, x-1) \rightarrow (x-1, x)$, in which case $Q$ is unchanged. But (*) cannot be performed infinitely many times.

anantmudgal09, I don't think your solution is right because of this part anantmudgal09 wrote: $$(x, y) \mapsto (y+1, x) \Longrightarrow S'=S+1-2(x-y)<S,$$ well, we can't find out the variation of S because the "y+1" part causes a lot of change... Can you understand?

tuvie wrote: There was something nice about this problem in the shortlist, that with the following statement could have been a medium-difficult problem in IMO 2012: Show that considering only the number of positive integers, she can perform at most $n^{n-1}$ (i think, it has been written by Carlos di Fiore as a comment ). Show that this cant be better. Any ideas about this?

Am I doing something wrong cause this looks too easy. Let M be the number with the maximum value out of the original sequence of numbers. Notice that M will always remain the maximum. Suppose we consider all moves of Alice which include M. WLOG assume that Alice carries out these moves one after the other. Then after each move $M$ will move one place to the right, and so, in the end, it will reach the rightmost corner. Now we can ignore M, as no more moves can have M. So consider only the numbers to the left of M. Redefine M to be the maximum out of these remaining numbers. Again follow the same steps as above. Then after some finite number of steps (as the total number of integers is constant and finite), an increasing sequnce of positive integers will be obtained, thus proving that Alice can perform only finitely many such operations.

This is a fun application of monovariants, as for commentary. Let the positive integers form the sequence $a_1, a_2, \ldots, a_n$, and look at the sum $S=\sum_{k=1}^n ka_k$. Let $x$ and $y$ be consecutive numbers in this sequence with $x > y$, if such consecutive numbers exist. Suppose $x=a_{\ell}$ and $y=a_{\ell+1}$. Then, the move $(x, y) \rightarrow (y+1, x)$ changes the sum from $S$ to $S+(y+1-x)\ell+(x-y)(\ell+1)=S+x-y+\ell>S$, so $S$ increases with this move. Similarly, the move $(x, y) \rightarrow (x-1, x)$ changes the sum from $S$ to $S+(x-1-x)\ell+(x-y)(\ell+1)=S+(x-y-1)\ell+(x-y)>S$, so $S$ also increases with this move. All in all, $S$ increases with any move. Let $M$ be the maximum value in the sequence $a_1, a_2, \ldots, a_n$. Clearly, at any time, $S$ has an upper bound of $M \cdot \frac{n(n+1)}{2}$, so $S$ can increase only a finite number of times. This means that only a finite number of moves can be applied, which completes the proof.

We will use induction. For $n=0$ it is trivial (0 steps). Let $f_n$ denote the maximum number of steps for a sequence length $n$. Now, let $M$ denote the maximum number in a sequence length $n$. Note that if we remove $M$, we will get a sequence length $n-1$. Hence, it is equivalent to show that there is a finite number of moves when we add a maximum to $n-1$ numbers. Note that $M$ can only move right, so there are at most $S=\sum_{k=0}^{n-1} f_{k}+k_{n-1-k}$ number of steps to until there are no more possible steps ($M$ is placed on the leftmost spot), which is finite, and we are done. $\blacksquare{}$

We will use induction on the number of terms in the sequence. Base case: There is only $1$ term. This is trivial as the sequence is already terminated. Inductive hypothesis assume this is true for $n-1$ terms. We will show it is true for $n$ terms. Consider the greatest term because of the inductive hypothesis we will always eventually need to have a move with the greatest term call it $x$ eventually. for $x>y$ if we perform an operation $x$ must move to the right and the term on the left will be less than it. So eventually $x$ will move to the far right and the sequence will stop by our inductive hypothesis and we are done.

I will prove the much stronger version where the numbers $(x, y)$ Don't have to be adjacent. Let $a_1, a_2, \cdots, a_n$ be the initial numbers on the row. Observe that the maximal element $k = max({a_1, a_2, \cdots, a_n})$ Does not change over the iterations. Let $w = \overline{a_1 a_2 \cdots a_n}$ be a number written in base $k+1$. Observe that the number $w$ strictly grows over the iterations and cannot grow over $W = \overline{kk \cdots k}$ (In base $k+1$), so the process must terminate over a finite number of iterations.

We prove a stronger result: Notice that the values of the terms don't really matter, the operation just rearranges the order of increase-decrease pairs by 1 every time. Hence we can renumber the terms as a permutation of (1,2,...,n), with the footnote that ties can be broken by letting a<b if a is to the left of b (this doesn't affect anything, because you won't apply process to equal terms anyways). Indeed, since there are only n! permutations and each operation iterated won't repeat, there are at most n!<n^n operations. (in fact the original result is just shown by saying that the operation rearranges a>b with a left of b to c<d with c left of d, hence the "number" read by each of the values from left to right is strictly decreasing and must terminate the operation.)

It is easy to see that the maximum number in the row is an invariant. Also, the sum of $a+2b+3c+4d....$ (from left to right) is a strictly increasing. However, we see that the maximum number can only move to its right and its moving must terminate after a certain number of moves. Thus the algorithm must terminate after finitely many iterations.

$\color{magenta} \boxed{\textbf{SOLUTION C1}}$ Let $a_1,a_2,...a_n$ be the numbers with $a_m=M$ be the maximum of them. $\color{red} \textbf{Claim 1 :}$ Maximum number $M$ never increases. $\textbf{Proof :}$ As $x>y \implies x \ge y+1$ Hence after each move the new two numbers are less than or equal to $x,$ So $a_m=M$ can't increase $\square$ $\color{red} \textbf{Claim 2 :}$ $\sum_{i=1}^{n} ia_i$ increases in every step. $\textbf{Proof :}$ $\textbf{1.}$ If $(x,y)$ is replaced by $(y+1,x),$ $$ix + (i + 1)y < i(y + 1) + (i + 1)x \iff y < i + x$$ which is true as $y <x$ $\textbf{2.}$ If $(x,y)$ is replaced by $(x-1,x),$ $$ix+(i+1)y < i(x-1)+(i+1)x \iff iy+y<i(x-1)+x$$ which is true as $y \le x-1, y<x \square$ But, $$\sum_{i=1}^{n} ia_i \le \sum_{i=1}^{n} iM= \frac{Mn(n+1)}{2}$$ So, the number of steps are finite $\blacksquare$

FTSOC assume otherwise. Both operations preserve the maximum value in the row. Alice can only perform the first operation finitely since it always increases the sum of all numbers by $1$. Alice can also only perform the second operation finitely when $x > y+1$ since it also increases the sum of the numbers. So, Alice must perform the second operation when $x = y+1$ infinitely many times – after some point, her moves will only be the second operation on $x=y+1$. But then the second operation effectively inverts $x$ and $y$, which can only be done finitely – contradiction.

How do you guys come up with all these weird monovariants :/ Anyhoo, this is my solution (please work): Let the numbers be $x_1, \cdots , x_n$ in that order. Claim 1: $\sum x_i$ is nondecreasing. Proof: For the first operation, $\sum x_i$ increases by 1. For the other one, the sum is nondecreasing as $y \le x-1$. It follows, then, that the sum is the same iff $y = x-1$. $\square$ Claim 2: $\sum x_i$ is bounded. Proof: Note that no element is ever larger than the initial largest element $X$ at any point in time. Therefore, $\sum x_i \le nX$. $\square$ Note that due to these two claims, eventually we must only perform operations of the form $(a-1, a) \to (a, a-1)$. But now notice that at this stage there are only finitely many pairs $(a-1, a)$, and once we perform the operation $(a-1, a) \to (a, a-1)$, we cannot get $a-1$ to the left of $a$ again, as that would require firstly getting them to be adjacent to another, but after that we can't perform the operation on them. From this reasoning, we can say that there are only finitely many moves after this, and we are done. $\square$

Let $a_i$ be the number at position $i$. Assign weight $2^i$ to the number at position $i$. Consider the weighted sum, $\sum a_i\cdot2^i$, we claim that it's monovariant. Let $2^k$ be the weight at $x$, $2^{k + 1}$ be the weight at $y$. After a move, our weighted sum takes one of the changes: $$2^kx + 2^{k + 1}y \rightarrow 2^k(y + 1) + 2^{k + 1}x, 2^k(x - 1) + 2^{k + 1}x$$ Note that both of these are greater than the initial, so our weighted sum takes an increase after each move. However, our largest number initially never changes, so our weighted sum is bounded, therefore we are done. $\square$

We prove this by induction on the number of elements. The base case of $n = 1$ is obvious. Inductive Step: We induct on the difference between the maximum and minimum elements. When the difference is zero, we are obviously done. Now we show if the difference is greater than $0$, we can either reduce to a case with a smaller difference or a smaller number of elements. Note that the maximum is invariant, so we focus on increasing the minimum. Let the minimum of the integers be $m$. If all integers with value $m$ eventually receive the first type of operation, we are done, since each of those operations strictly decreases the number of integers with value $m$ by $1$. If any of them don't receive the first type of operation, they must only receive the second operation. Assume further that some element exists that has value $m$, and only receives the second operation when $x = m + 1$, otherwise we would still decrease the number of integers with value $m$ by $1$ (if such an element does not exist we just got rid of all integers with value $m$). If this element receives a finite amount of operations, we are done, since after the last operation we can only operate a finite number of times (we already showed this for one fewer element). If this element receives an infinite number of operations, each operation effectively just switches two integers where one is $m$ and the other is $m +1$, notably forcing the integer with value $m$ to be moved further up the row, so this can obviously not happen an infinite number of times.

this should work right?

Consider all possible permutations of the numbers, and order them lexicographically. Call this list $S.$ Clearly each move takes the current permutation on some fixed direction either up or down $S.$ But $S$ is finite and thus Alice can only perform a finite amount of moves. QED

For any set of numbers, consider the bijection $T$ (from the set of $n$ numbers of the board to $\{1, 2, \cdots, n\}$): - if $a > b$ then $T(a) > T(b)$ - $a=b$ but $a$ is left of $b$ For set of numbers on the board $C = (x_1,cdots, x_n)$, after making a move to get $C'$ config, notice that: $T(C')$ is lexicographically smaller than $T(C)$. Since there are $n!$ permutations, it should take at-most $n!$ steps and we are done.