By the way you typoed '10

My first thought was the USAMTS problem, it's actually somewhat similar.

Just to drive a point home

I didn't take the USAMO officially, but here is the solution I came up with, not necessarily well written, but I believe to be correct. First, note that because the tallest person cannot pass the second tallest person, that person can only move forward as many spaces as the second tallest, plus n-2 if he initially starts in front of the second tallest person. This maximum can be reached by moving around the circle once and then following the second tallest person every time they move. Now, let a(n) be the maximum number of moves before there are no more. The maximum distance moved for the tallest person is a(n)-a(n-1), because the tallest person is adding their moves to the solution for a(n-1). This along with the previous comment gives the recurrence relation a(n)-a(n-1)=n-2+a(n-1)-a(n-2). Along with the base cases of a(1)=a(2)=0, the solution to this recurrence is n chose 3, as can be shown by substituting into the relation.

CatalystOfNostalgia wrote:

exactly my solution

Can't you just do the following? Say they are all standing in a circle looking clockwise. You can check that the clockwise order of each triple of people can change at most once. (This boils down to the case n=3). Then, QED.

Whoops. That is false. Never mind. Should probably think a little more before posting...

I didn't actually take the USAMO, but here's a nice solution I found. I think it's more direct than the solutions posted already, but it's not necessarily easier.

let h_{k} be assigned to the heights in increasing order. it can be seen that the only position in which no further moves can be made is n, n-1, n-2,... 4, 3, 2, 1. Because if n cant make a switch then n-1 is infront of it. Assume K cant make a switch and all elements greater than k are behind K then k-1 is in front of k. Now consider reversing the problem such that u can switch 2 numbers h_{k}, h_{m} if h_{m}>h_{k}+1. The only position in which there are no remaining moves is 1, 2, 3, 4,....n-2, n-1, n by a similar argument. This means that any arrange can reach 1, 2, 3, 4... n-2, n-1, n and vice versa. Now we must show that the maximum number of moves it takes for 1, 2, 3, 4, ... n-2, n-1, n to reach n, n-1, n-2,... 4, 3, 2, 1 is n choose 3. Note that if h_{k} > h_{j}+1 and h_{k} can swap places with h_{j} p times, then h_{k+1} can swap places with h_{j} p+1 times because in the initial position h_{k+1} will swap places with h_{j} before h_{k} does and thereafter it can swap places with h_{j} once more for each time h_{k} can because h_{k+1} can make any swap h_{k} can. If h_{n} is the max we can see that the number of swaps for h_{n} is n-2+n-3+n-4...+1=(n-2)(n-1)/2. Similarly h_{n-m}=n-m-2+n-m-3+...1=(n-m-2)(n-m-1)/2. Sum of (n-m-2)(n-m-1)/2 as m goes from 0 to n-3 (h_{2}, h_{1} cant swap at all) is by the hockey stick formula n choose 3.

i don't know if my solution is same as aboves, anyway this is the sketch of my solution : a_i is one who has got the weight h_i for aiming n(n-1)(n-2)/6 : just stand students in decreasing order of weights clockwise, then take a_n and switch it as much as you can,its number of switches is n-2,then take a_n-1 , switch it as much as you can and then again a_n and so on, the numbers you get are : n-2 n-3,n-3 n-4,n-4,n-4 . . . 1,1,...,1 (n-2 times) the sum of above numbers is equal to n(n-1)(n-2)/6 by Cauchy-chee (i guess) lemma. for proving the maximality define a directed graph G-n with n-vertices where each of it's vertices are the ordering-shape of these students arround the circle, and vertex u leads to vertex v if we can change the shape-u by the moves defined by the problem to the shape-v. then use induction with n to get that we there is a leading edge from the related vertex of the shape defined for proving "arriving to n(n-1)(n-2)/6" to any other vertex and so it's Done!

AceOfDiamonds wrote: For any given starting position, there is exactly one set of moves that will take it to the ending position. In other words, the order in which moves are performed doesn't matter. Sorry, I don't see why this is true. Could you explain a little?

v_Enhance wrote: AceOfDiamonds wrote: For any given starting position, there is exactly one set of moves that will take it to the ending position. In other words, the order in which moves are performed doesn't matter. Sorry, I don't see why this is true. Could you explain a little? intuition? in bubble sort the inversions are all reversed 1 by 1, so i figure there should be something similar going on here. (i don't have a proof--black moppers pls help)

$\textbf{Claim: }$ For all $j>i$, $h_j$ can swap with $h_i$ at most $j-i-1$ times. (Note that if $j=i$ no swaps are allowed, and $j<i$ swaps are symmetrical to $j>i$ swaps.) We proceed with induction on $j-i$. For our base case note that if $j-i=1$, we clearly can never swap. For $j-i\geq 2$, consider $h_j$, $h_i$, and $h_{i+1}$. Note that $h_j$ can swap at most one more time with $h_i$ than with $h_{i+1}$ since in order for $h_j$ to swap with $h_i$ twice in a row, $h_j$ must make a full circuit which will clearly pass over $h_{i+1}$, and $h_{i+1}$ cannot escape past $h_i$. Thus, we have by the inductive hypothesis that the number of swaps is at most \[\text{swaps}(i,j) \leq 1 + \text{swaps}(i+1,j) \leq 1+ (j-(i+1)-1) = j-i-1\]thus our induction is complete, and the total number of swaps is at most \[\sum_{j>i} i-j-1 = \sum_{j>k>i} 1 = \binom{n}{3}\]and we are done.

request move to P2P

DottedCaculator wrote: request move to P2P pls no they might actually do it

We proceed with induction. The base case $n=3$ is trivial. For the inductive step, call the tallest student Bob; we claim that Bob can move at most $\binom{n}{2}$ times, which completes the induction by Pascal's formula. Indeed, Bob can move at most $n-1$ times before getting stuck behind the student with height $h_{n-1}$ (call him Bobb), and Bobb can move at most $\binom{n-1}{2}$ times by our inductive hypothesis.

1=2 wrote: There are $n$ students standing in a circle, one behind the other. The students have heights $h_1<h_2<\dots <h_n$. If a student with height $h_k$ is standing directly behind a student with height $h_{k-2}$ or less, the two students are permitted to switch places. Prove that it is not possible to make more than $\binom{n}{3}$ such switches before reaching a position in which no further switches are possible. Claim:- The students with heights $h_i$ and $h_j$ switch at most $|j-i|-1$ times. Proof:- Induct on $d = |j-i|$.Assume WLOG $j > i$. For $d = 1$ there is nothing to prove. For $d \ge 2$, look at only students $h_j$, $h_{i+1}$ and $h_{i}$ ignoring all other students. After $h_j$ and $h_i$ switch the first time, the relative ordering of the students must be $h_i \to h_j \to h_{i+1}$. Thereafter $h_j$ must always switch with $h_{i+1}$ before switching with $h_i$, so the inductive hypothesis applies to give the bound $1 + j - (i+1) - 1 = j-i - 1$. $\blacksquare$ Hence the maximum moves is \[\sum_{1\leq 1 < j \leq n} (|i - j| - 1) = \sum_{i = 2}^{n-1} \binom{i}{2} = \binom{n}{3}\],as required.$\blacksquare$

The main idea is to find a good upper bound on the number of swaps in positoins that two given students make. The rest is just globally summing this up and achieving the answer. We claim that the students with heights $h_i, h_j$ with $i < j$ switch at most $j-i-1$ times. We induct on $j-i$. Clearly the result holds for $j = i+1$, henceforth assume $j \geqslant i+2$. Let us focus only on the circle formed by the students with heights $h_i, h_{i+1}$ and $h_j$. It is clear that the relative order of $h_i, h_{i+1}$ is fixed for they never swap places. Thus throughout the process it is $h_j$ which moves "through" these. There are $2$ ways for $h_j$ to go through $h_i$. It either directly goes to $h_i$ from its "open" side, or it passes through $h_{i+1}$ and then swaps with $h_i$. (notice that $h_{i+1}$ in some sense is a protection for $h_i$) Since the latter happens at most $j-i-2$ times and the former at most once the induction is complete. Now to finish simply note that: \[\sum_{1 \leqslant i < j \leqslant n} (j-i-1) = {n \choose{3}}\]

Note that if no further switches are possible, then $h_n$ can only stand behind $h_{n-1}$, therefore $h_{n-1}$ can only stand behind $h_{n-2}$, and so on. So the final arrangement is fixed, i.e. $h_1, h_2, \ldots h_n$, with everyone facing the left (in the above sequence) and $h_1$ facing $h_n$. In a switch, call the taller student the one who is 'making' the switch/moving. (Imagine that the taller student is jumping over the shorter one.) Let the maximum number of people $h_k$ can jump over (i.e. the number of moves she makes in the config in which she makes the maximum number of moves) be $f(k)$. Now, it is easy to see that without $h_{k-1}$ moving, $h_k$ can only move maximum $k-2$ times (since it can only jump over the $k-2$ people shorter than $h_{k-1}$). Now if $h_{k-1}$ jumps over someone, then $h_k$ can jump over that person, too. Then $f(k)\le k-2+f(k-1)$. In the worst case scenario (when $f$ is maximised) $f(k)=k-2+f(k-1)$. So let us assume that equality does hold (absolute worst case) and define $f$ that way. (Notice that $n$ does not affect $f(k)$, also long as $k\le n$.) Therefore $f(1)=f(2)=0, f(3)=1, f(4)=3$ and so on. It can be proven by induction that $f(k)=$$k-1\choose2$. So for $n$, the maximum possible number of switches possible is $\Sigma^{n}_{k=1} f(k) = \Sigma^{n-1}_{i=2}$$i\choose2$ = $\Sigma^{n-2}_{j=1} \frac{j^2+j}{2}$ which upon computing is equal to $n\choose3$.

nice problem, solved with HoRI_DA_GRe8 and kamatadu.

We claim that the maximum amount of times students with heights $h_i$ and $h_j$ can switch places is $|i-j| -1$. This is equivalent to the problem since \[\sum_{1 \leq i < j \leq n} |i-j| - 1 = \binom{n}{3}\] Now we prove the claim. We prove the result by induction on $|i-j|$. Our base case is trivial. Consider only $h_i$, $h_j$, and $h_{j+1}$ wher $i > j$. Notice that whenever $h_i$ and $h_j$ switch spot $h_i$, $h_j$, and $h_{j+1}$ must be in the order $j$, $i$, $j+1$. Thus after the first switch $h_i$ must always switch with $h_{j+1}$ before switching with $h_j$. Since $|i -(j+1)| - 1 +1 = |i-j| - 1$ our induction is complete.

For clarity, let $s_k$ refer to the student with height $h_k$. Claim: For two students $s_i$ and $s_j$, with $i>j$, they can swap places at most $i-j-1$ times. Proof: For any given $j$, induct from $i=j+1$ to $i=n$. The base case of $i=j+1$ is true because $i-j-1=0$ and the students can never swap due to the given rule. For the inductive step, we assume $i\geq j+2$. We notice that right after student $s_i$ swaps with student $h_j$, all other students, including student $s_{i-1}$, are in the way of $s_i$ and $s_j$ swapping again. Since students $s_i$ and $s_{i-1}$ can never swap, $s_i$ cannot swap with $s_j$ again until $s_{i-1}$ swaps with $s_j$ to get out of the way. By our inductive hypothesis, $s_{i-1}$ can swap with them at most $i-j-2$ times, so then $s_i$ can swap with them at most $i-j-1$ times, adding $1$ for the first swap which isn't restricted. This completes our induction. Now we just need to sum up $i-j-1$ over all pairs $(i,j)$ with $1\leq j<i\leq n$. To do this, note that $i-j-1$ is the number of students with heights between $h_i$ and $h_j$, so there is a bijection between this sum and the number of ways to choose two students, then one between them. This is equivalent to the number of ways to choose three students, or $\binom{n}{3}$. Thus there can be at most $\binom{n}{3}$ moves, as desired.

Denote the student with height $h_i$ by $s_i$, and say that each student faces clockwise along the circle. Key Claim: For all $1 \le i < j \le n$, $s_i$ is swapped with $s_j$ at most $j - i - 1$ times. Proof: We use induction on $j - i$. The base case is when $j - i = 1$, where $s_i$ cannot be swapped with $s_j$. Now suppose $j - i > 1$. Then at any time, the circle could be in two types of states: type A, where $s_i$, $s_{i+1}$, and $s_j$ are in clockwise order, and type B, where $s_i$, $s_{i+1}$, and $s_j$ are in counterclockwise order. We move from a type A to a type B state when, and only when, we swap $s_i$ and $s_j$; similarly we move from a type B state to a type A state when, and only when, we swap $s_{i+1}$ and $s_j$. These are the only cases where swapping $s_i$ with $s_j$, or $s_{i+1}$ with $s_j$, is possible. Therefore we must alternate between swapping $s_i$ with $s_j$, and swapping $s_{i+1}$ with $s_j$, since these swaps correspond precisely with changes between type A and B states. Therefore $s_i$ is swapped with $s_j$ at most one more time compared to swapping $s_{i+1}$ with $s_j$. But $s_{i+1}$ is swapped with $s_j$ at most $j - i - 2$ times by the inductive hypothesis, so $s_i$ is swapped with $s_j$ at most $j - i - 1$ times. $\square$ Taking the sum of this bound over all $1 \le i < j \le n$ gives the desired result.

We will first show that the maximum number of swaps $h_j$ and $h_k$ can make with eachother is $|j-k| - 1$, via induction. Our base case of $k = j - 1$ is true, as clearly there are $0$ possible swaps. For our inductive step, we will show that if $h_j$ and $h_k$ can make $m$ possible swaps, then $h_j$ and $h_{k-1}$ can make at most $m+1$ swaps. Note that $h_k$ and $h_{k-1}$ can never swap, so $h_j$ can swap with $h_{k-1}$ once, and cycle back $m$ times through $h_{k}$ to get a total of $m+1$ swaps. Then we sum $j - k - 1$ for all $j > k$ to get $(1 + 2 + \dots + n - 2) + (1 + 2 + \dots + n - 3) + \dots + 1 = \sum_{i=2}^{n-1} \binom{i}{2}$ which is just $\binom{n}{3}$ as desired.

Claim : The maximum number of swaps between $h_i$ and $h_j$ (where $j>i$) is $j-i-1$ Pf: We prove that with induction, base case is trivial. Now let assume that $h_i$ and $h_j$ swap $x$ times We show that $h_i$ and $h_{j-1}$ swap $x+1$ times. Which is easy to do. Now We will be left with. \[\sum_{1 \leq i < j \leq n} i-j - 1\]Which is equal to. \[\sum_{1 \leq i < j \leq n} i-j - 1= \binom{n}{3}\]As desired.

Claim: For any different integers $1 \le x,y \le n$, $h_x$ and $h_y$ cannot swap more than $|x-y| - 1$ times. Proof: Suppose otherwise. Let $k$ be the smallest possible positive integer so that there exist integers $1 \le x, y \le n$ so that $|x-y| = k$ and $h_x$ and $h_y$ could swap at least $k$ times. First note that $k > 1$. WLOG that $x > y$, so $x = y + k$. Now consider any two consecutive swaps between $h_{y + k}$ and $h_y$. Note that in between these two swaps, one of $h_y, h_{y + k}$ must swap with $h_{y + 1}$. Since $h_y$ and $h_{y + 1}$ cannot swap, $h_{y + 1}$ must swap with $h_{y + k}$. However, this can happen at most $k - 2$ times, so there can only be at most $k - 2$ pairs of two consecutive swaps between $h_{y + k}$ and $h_y$, implying at most $k - 1$ swaps between $h_{y +k}$ and $h_y$. Therefore, such $k$ does not exist, so the claim is true. $\square$ Since any swap must involve $h_x, h_y$ with $1 \le x < y \le n$, the number of swaps is at most \begin{align*} \sum_{1 \le x < y \le n} (|x-y| - 1) = \sum_{1 \le x < y \le n } (y - x - 1)\\ = \sum_{1 \le x < y \le n} y - \sum_{1 \le x < y \le n} x - \sum_{1 \le x < y \le n} 1 \\ = \sum_{1 \le y \le n} y(y - 1) - \sum_{1 \le x \le n} x(n - x) - \binom n2 \\ = \sum_{1 \le y \le n} (y^2 - y) - \sum_{1 \le y \le n} (yn - y^2) - \binom n2 \\ = \sum_{1 \le y \le n} (2y^2 - y(n+1)) - \binom n2 \\ = \frac{n(n+1)(2n+1)}{3} - \frac{n(n+1)^2}{2} - \frac{n(n-1)}{2} \\ = \frac n6 \cdot (2(n+1)(2n+1) - 3(n+1)^2 - 3(n-1)) \\ = \frac{n(n-1)(n-2)}{6} = \binom n3 \\ \end{align*} (the $1 \le y \le n$ and $1 \le x \le n$ in the third line are fine because $y(y-1) = 0$ when $y = 1$ and $x(n-x) = 0$ when $x= n$)

For simplicity, replace $h_i$ with its index $i$. The main claim is that two heights $a$ and $b$ swap at most $swap(a,b) = |a-b|-1$ times, from which summing across all $(a,b)$ gives the desired bound. First note that $(a,b)$ with difference 1 can clearly never swap. Otherwise, notice that after $(a,b)$ swap the first time, each other number from $1, \ldots, n$ must swap with one of $a$ or $b$ in order for the two to swap again. Hence we have the bound \[swap(a,b) \leq 1 + \min_{c \neq a,b}(swap(a,c) + swap(b,c)),\] from which inducting downwards gives the desired. $\blacksquare$