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.
Problem
Source:
Tags: USA(J)MO, USAMO, induction, monovariant, USAMTS
29.04.2010 16:41
29.04.2010 18:05
By the way you typoed '10
29.04.2010 18:14
29.04.2010 18:36
My first thought was the USAMTS problem, it's actually somewhat similar.
29.04.2010 20:13
02.05.2010 02:16
Just to drive a point home
02.05.2010 02:28
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.
02.05.2010 02:40
CatalystOfNostalgia wrote:
exactly my solution
09.05.2010 01:55
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.
09.05.2010 02:03
Whoops. That is false. Never mind. Should probably think a little more before posting...
10.05.2010 10:47
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.
16.10.2010 04:42
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.
12.02.2013 19:36
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!
05.09.2013 06:17
06.09.2013 09:17
06.09.2013 16:56
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?
07.09.2013 05:42
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)
09.03.2014 05:35
08.04.2014 04:07
30.05.2021 21:38
$\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.
30.05.2021 21:40
request move to P2P
30.05.2021 21:43
DottedCaculator wrote: request move to P2P pls no they might actually do it
16.09.2021 21:13
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.
28.10.2021 09:34
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$
05.01.2022 11:27
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}}\]
21.11.2023 00:08
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$.
20.12.2023 22:40
nice problem, solved with HoRI_DA_GRe8 and kamatadu.
13.02.2024 07:33
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.
06.06.2024 22:20
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.
25.06.2024 23:49
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.
07.07.2024 05:14
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.
12.08.2024 17:50
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.
30.10.2024 17:16
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$)
04.01.2025 23:52
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$