Hint: Each time you apply the procedure, the number of "inversions" (i.e., pairs $\left(i, j\right)$ of two students $i$ and $j$ such that $i$ is further left than $j$ but is shorter than $j$) decreases, unless the students are already arranged in the order of descending height. EDIT: Oops, this is useless.

It's a trivial observation, but what does it help us?

Fix $k\in R_+$, we replace all the student with he height less than $k$ by number $0$, the others will be replaced by $1$. Call the place between $1$ number $0$ and $1$ a junction. The weight of a junction is the number of $0$ to the left plus the number of $1$ to the right. The possible values of weight are from $2$ to $N$. Each junction is inside a group and no group have two junction. After a procedure, all junctions are on the border of the group which had contained junctions, and their weights is less than the weight of the junction in the corresponding group. So the maximum value of weight will decreases, then there are no junctions after $N-1$ procedure and all the $1's$ is to the left of $0's$. By considering the values of $k$, the children in the line would stand from the left to the right in descending order of their heights after $N-1$ procedure

Yes, it's the official solution. I've seen it after some unsuccessful tries. The clever point here is to fix some threshold and to see that on a place of inversion, some quantity, which is at most $N-1$, decreases. But if you just count the inversions- there can be many of them and the fact that they decrease helps nothing to us.

dgrozev wrote: Yes, it's the official solution. I've seen it after some unsuccessful tries. The clever point here is to fix some threshold and to see that on a place of inversion, some quantity, which is at most $N-1$, decreases. But if you just count the inversions- there can be many of them and the fact that they decrease helps nothing to us. Do you know where are the solutions of all the ToT problems ?

I searched and found it here: http://sasja.shap.homedns.org/Turniry/TG/index.html It's in russian.

Juviette wrote: dgrozev wrote: Yes, it's the official solution. I've seen it after some unsuccessful tries. The clever point here is to fix some threshold and to see that on a place of inversion, some quantity, which is at most $N-1$, decreases. But if you just count the inversions- there can be many of them and the fact that they decrease helps nothing to us. Do you know where are the solutions of all the ToT problems ? And here

At any point in time, we will say that the children are $i-$obedient if the $i$ shortest people are the $i$ rightmost people. It suffices to prove that the children are $i-$obedient after $N-1$ rearrangements, for all $1 \le i \le N.$ Our strategy will be to fix some arbitrary $1 \le i \le N$, and show that the children are $i-$obedient after $N-1$ arrangements. Let us give the $i$ shortest children red hats and the remaining $N-i$ children blue hats. We know that every move that we perform will be on a contiguous group of children $G$, so that subset of $G$ with red hats is exactly the leftmost $x$ students of $G$ for some $x.$ Now, rather than having each child stick to their own hat, we will impose the following strange rule. If we perform a move on the children of the set $A \cup B$, where $A, B$ are contiguous sets of children with red, blue hats so that the rightmost child in $A$ is to the left of the leftmost child of $B$, then we will first reverse the children as in the problem. However, the hats move as follows. Each red hat moves to the right by $|B|$, while each blue hat moves to the left by $|A|.$ In particular, if we reverse a block of students with either only red hats or only blue hats, the hats do not actually move. With this modification, it becomes clear that every red hat either stays put or moves to the right at any moment. We will say that a red hat has fulfilled if there are no blue hats to its right. The next observation is that every red hat which is immediately to the left of a blue hat must move right at each move. With these observations, we are prepared to solve the problem. Notice that we need only show that the leftmost red hat reaches the $(N-i+1)$th spot from the left after at most $N-1$ moves. Let's label the red hats $h_1, h_2, \cdots, h_i$ from left to right. Notice that if $h_j$ and $h_{j+1}$ are not adjacent to each other at any moment, they will never again be adjacent to one another until both hats have fulfilled their potential. This is easy to show with a downwards induction on $j.$ At any instant where $h_1$ is not fulfilled, we will let $k$ be a variable which denotes the smallest positive integer $k$ so that the hat $k$ positions to the right of $h_1$ is blue. After this observation, we are prepared to prove the claim. We claim that at each instant when $h_1$ is not fulfilled, either $k$ decreases or $h_1$ moves to the right. This is immediate upon considering the rightmost hat among the block of $k$ consecutive hats starting at $h_1.$ With this observation, it's clear that it takes at most $(k_0 - 1) + N-i$ moves for $h_1$ to fulfill, where $k_0$ is the initial value of $k$. This is because $h_1$ moves right at most $N-i$ times and $k$ decreases at most $k_0 - 1$ times. Since $k_0 \le i$ is obvious, we have obtained our desired bound of $N-1$. Combining the previous results and removing hats, the $i$ shortest students are the $i$ rightmost students in the line after $N-1$ moves, for every $1 \le i \le N.$ This implies that the students are in descending order, so we're done. $\square$

Solution from Twitch Solves ISL: We will use a threshold trick: fix a threshold $1 \le k < N$, and during the process write $0$ for heights at most $k$ and $1$ for heights greater than $k$. We are going to prove that under this process, the $1$'s end up before all the $0$'s after at most $N-1$ steps. (Note that the exact steps of the process depend on the original numbers, and are not a function of $0$/$1$). An example is given below for $N = 7$, with the original heights on the left and the modified process on the right for $k = 3$. \[ \begin{bmatrix} 2 & 7 & 3 & 1 & 4 & 5 & 6 \\ 7 & 2 & 3 & 6 & 5 & 4 & 1 \\ 7 & 6 & 3 & 2 & 5 & 4 & 1 \\ 7 & 6 & 3 & 5 & 2 & 4 & 1 \\ 7 & 6 & 5 & 3 & 4 & 2 & 1 \\ 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \end{bmatrix} \longmapsto \begin{bmatrix} 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ \end{bmatrix} \]Then, by varying the choice of $k$, the problem will be implied. However, for fixed $i$, we prove the following claim: Claim: Suppose $0 \le i < k$ and $t \ge i$. After $t$ steps, the $(i+1)$st zero from the right is in position at least $\min(k + t - 2i, n-i)$. Proof. Basically immediate by induction on $i$. $\blacksquare$ Applying this claim ends the problem.

This solution will contain three distinct but related stages, in which we view the swapping process in a different way for each stage. Stage 1: Suppose the childrens' heights are $1,\ldots,N$. We will prove by induction on $k\geq 1$ that the child with height $k$ ends up in the right spot, with the base case of $k=1$ being clear, since if this child is not currently in the rightmost position, it must move rightwards. For the inductive step, observe that by hypothesis we guarantee that any children with height less than $k$ end up to the right, so it suffices to show that any children with height greater than $k$ end up to the left. However, at this point the specific heights are not very important, so replace every student with height at most $k$ with a letter $A$ and every student with height more than $k$ with a letter $B$. It then suffices to prove the following. Stage 2: Suppose we are given a word containing $a$ copies of $A$ and $b$ copies of $B$ (and nothing else). In a move, we select some substrings of the word such that The substrings are all disjoint, Every substring is of the form $A\ldots AB\ldots B$ (the number of $A$s and $B$s must be positive), Every occurrence of $AB$ must appear in some substring. Then we take each substring and swap the positions of the $A$s and $B$s. This corresponds to a subsequence reversal, but instead of reversing we simply shift the $A$ and $B$ blocks, so that during a move the relative position of any two $A$s doesn't change, nor does the relative position of any two $B$s. It is clear that some choice of moves will correspond to the original process, hence it suffices to prove that after $a+b-1$ moves we are guaranteed to have every $B$ appear to the right of every $A$. Define the deadwall to be a set of characters as follows: if the rightmost character is a $B$, then the deadwall is empty. Otherwise, it is the maximal contiguous set of $A$s containing the rightmost character. Furthermore, say that a character is a dummy on a move if it remains stationary (i.e. is not selected in a substring). I will show that, before becoming part of the deadwall, the leftmost $A$ can only be a dummy at most $a-1$ times. This will finish the problem: whenever it is not a dummy, at least one $B$ character moves from the right to the left of the leftmost $A$. Therefore, if after $a+b-1$ turns the leftmost $A$ is not part of the deadwall, it will have at least $b$ $B$s to its left: contradiction. To prove this claim, it clearly suffices to consider the following modification (since deadwall characters only "interact" with other deadwall characters). Stage 3: Suppose that we take the definition of a move from stage 2, but instead apply it to a word which is infinitely "padded" by the character $B$ to the right. For example, if the previous word was $ABAABBA$, then the new word is $ABAABBABBB\ldots$. I claim that the leftmost $A$ can only be a dummy at most $a-1$ times if we run this process indefinitely. To prove this, observe that every time the leftmost $a$ is a dummy, the number of connected "blocks" of $A$s must increase by at least $1$: we have the leftmost $A$ in a block, as well as one new block corresponding to the $A$s that got moved in each old block. Since we have at least one block and at most $a$ blocks, it follows that the leftmost $a$ can be the dummy at most $a-1$ times. We are done. $\blacksquare$ Remark: I think this solution is fairly natural to come up with and does not require the rather difficult-to-spot observations in some solutions. In some sense, we are trying to get at the essence of this process. First, after the induction, the actual numbers are no longer important to the essence, and we get a much simpler structure. The deadwall is also something that is noncentral to the essence of the process, and serves as somewhat of an obstruction to visualizing constructing arguments. By essentially ignoring it, it becomes clear how to solve the problem in stage 3. Despite this naturalness, I think this problem is quite difficult: in some sense, the processes all feel quite natural already, and there was often an "intuitive" feeling of claims that really look true (and probably are true) which I couldn't prove. EDIT: ok I guess if you keep the original heights in mind instead of discarding them for stage $2$ you can actually prove that when two $A$s separate they won't come back together, and there are a lot of ways to finish from here. Unfortunately this is not true if you actually ignore the heights, because you have the annoying counterexample $AAABB \to ABAAB \to BAABA$. There is a valuable lesson to be learned here as well.

I'm actually so bad. Give the children $\le i$ a red hat and the rest a blue hat. It remains to show inductively that after $n - 1$ moves, all the red hat children are at the right. Each group consists of students with red hats followed by those with blue hats. Redefine the inversion operation to instead simply switch the position of red and blue students, preserving the order between red and blue students. Claim: Whenever a red student is to the left of a before a blue student, the red student must move over one. Proof. Follows immediately as the red and blue student are part of the same group. $\blacksquare$ Label the red students $r_i, \dots r_1$ from left to right. Claim: After $k$ turns, $r_i$ has moved at least $k - i$ turns unless it has reached $n + 1 - i$. Proof. Assume this holds for $r_i$. We prove this holds for $r_{i+1}$. Induct on $k$. Each turn, $r_{i+1}$ moves over unless it is blocked by $r_{i+1}$. If $r_{i+1}$ is at $n + 1 - i$, we are immediately done. Else, $r_{i}$ has moved at least the same amount over as $r_i$, which is $n - i$ as desired. $\blacksquare$ Thus, after $k = n - 1$ moves, $r_i$ has reached $\min\{t_i + n - i, n + 1 - i\} = n + 1 - i$ where $t_i$ is its starting position. The result follows. Additional Thoughts: Some old paper here proves this result, as well showing that $n$ moves are required when even.

I really liked this, the despair that you feel at beginning is very characteristic of this brand of combinatorics Gall the first $n$, small, and the rest big. The problem is implied by showing that all small end up in the end. Focusing only on the small, and big (ignoring the absolute position), and the $i$-th right leftmost small number, one can show that it will grow slightly bigger than $n' + C$, where $C$ is a constant that is convenient to solve the problem and $n'$ are the current turn we find ourselves in. And we are done $\Box$. Remark: the "solution" (I won't bother into making an actual solution) is almost entirely motivated by looking at the smallest number, and proving that it gets to the end with the obvious property, noticing that this generalizes and that the only thing that matters is the general classification simplifies by lots the problem.