Difference between revisions of "2010 USAMO Problems/Problem 2"

Latest revision as of 15:53, 31 August 2024

Problem

There are $n$ students standing in a circle, one behind the other. The students have heights $h_1 < h_2 < \ldots < 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.

Solution 1

We adopt the usual convention that $\binom{i}{j} = 0$ unless $0 \le j \le i$ . With this, the binomial coefficients are defined for all integers via the recursion:

$\binom{0}{0} = 1, \quad \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$

It is clear that the circle is oriented and all the students are facing in same direction (clockwise or counterclockwise). We'll call this direction forward.

In any switch consider the taller student to have moved forward and the shorter student to have remained stationary. No backward motion is allowed. With this definition of forward motion, the first two students with heights $h_1$ and $h_2$ are always stationary, while other students potentially move past them.

For $k > 2$ , the student with height $h_k$ can never switch places with the student with height $h_{k-1}$ , and the former can make at most $k-2$ more forward moves than the latter (when all the students of heights $h_1, \ldots h_{k-2}$ are between $h_k$ and $h_{k-1}$ in the forward direction).

Therefore, if the $(k-1)^{\mathrm{st}}$ student can make $s_{k-1}$ forward steps, the $k^{\mathrm{th}}$ student can make at most $s_{k-1} + k - 2$ steps. With $s_1 = s_2 = 0$ and $s_3 = 0 + (3-2) = 1$ , and a constant second difference of $1$ , we quickly see that $s_k = \binom{k-1}{2}$ .

With $n$ students in all, the total number of steps is therefore at most $\sum_{i=3}^{n}\binom{i-1}{2} = \binom{n}{3}$ , by the Hockey Stick Theorem

Solution 2

WLOG, let $h_k=k$ . Now, we find the end arrangement with the most switches possible. We claim that the arrangement will be $n,n-1,n-2,\dots ,1$ , where the left to right direction is the "backwards" direction. To prove this makes the most switches, we show that there is always at least one more switch that can be done for any other arrangement. This is elementary to show. There will always be one height $x$ such that the number to its right is $2$ less than $x$ , unless every number has $x-1$ to the right of $x$ (other than $2$ and $1$ ). The exception occurs at our claim, so our claim is proven. Now we want to find the maximum ways we can "undo" our arrangement. But undoing a switch is just doing a switch from our arrangement in the opposite direction. So, the start arrangement with the most possible switches is the reverse of the end arrangement or $1,2,3,\dots ,n$ . We want to find how many switches must be done to get from the start arrangement to the end arrangement. We start by switching $n$ around until it cannot be switched anymore. We find that we can switch $n$ $n-2$ times. When we are switching (or, in other words, moving to the right) the number $k$ , we can switch it $k-2$ times before it is to the left of $k-1$ . But then we can also switch each of $k+1,k+2,\dots ,n$ (in that order) $k-2$ times before they get stopped again. Let $x=n-k+2$ . Then, the sum of the switches is $\sum\limits_{x=2}^{n-1} (n-x)(x-1)=\sum\limits_{x=1}^{n} (n-x)(x-1)$ .

Rearranging and summing, we get $\sum\limits_{x=1}^{n} x(n+1)-\sum\limits_{x=1}^{n} n -\sum\limits_{x=1}^{n} x^2=\frac{n(n+1)^2}2-n^2-\frac{n(n+1)(2n+1)}6=\frac{3n(n^2+1)}6-\frac{n(n+1)(2n+1)}6=\frac{n(n^2-3n+2)}6=\frac{n(n-1)(n-2)}{3!}=\binom{n}{3}$

Comment

This process of switching is very similar to Bubble Sort, except that the terms must be in consecutive decreasing order, and wraps around $2,1,n,n-1\dots$ . This answer seems to disagree, though, because the worst case efficiency is $\mathcal{O}(n^2)$ , not $\mathcal{O}(n^3)$ .

https://en.wikipedia.org/wiki/Bubble_sort

@@ Line 1: / Line 1: @@
 ==Problem==
-There are <math>n</math> students is standing in a circle, one behind the
+There are <math>n</math> students standing in a circle, one behind the
 other. The students have heights <math>h_1 < h_2 < \ldots < h_n</math>. If a
 student with height <math>h_k</math> is standing directly behind a student
@@ Line 8: / Line 8: @@
 no further switches are possible.
-==Solution==
+==Solution 1==
-It is clear that the circle is oriented and all the students are facing in same direction (clockwise or anti-clockwise). We'll call this direction <i>forward</i>.
+We adopt the usual convention that <math>\binom{i}{j} = 0</math> unless <math>0 \le j \le i</math>.
+With this, the binomial coefficients are defined for all integers via the
+recursion:
+<center>
+<cmath>
+\binom{0}{0} = 1, \quad \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}
+</cmath>
+</center>
+It is clear that the circle is oriented and all the students are facing in same direction (clockwise or counterclockwise). We'll call this direction <i>forward</i>.
 In any switch consider the taller student to have moved <i>forward</i> and the shorter student to have remained <i>stationary</i>. No backward motion is allowed. With this definition of forward motion, the first two students with heights <math>h_1</math> and <math>h_2</math> are always stationary, while other students potentially move past them.
@@ Line 15: / Line 24: @@
 For <math>k > 2</math>, the student with height <math>h_k</math> can never switch places with the student with height <math>h_{k-1}</math>, and the former can make at most <math>k-2</math> more forward moves than the latter (when all the students of heights <math>h_1, \ldots h_{k-2}</math> are between <math>h_k</math> and <math>h_{k-1}</math> in the forward direction).
-Therefore, if the <math>(k-1)^{\mathrm{st}}</math> student can make <math>s_{k-1}</math> forward steps, the <math>k^{\mathrm{th}}</math> student can make at most <math>s_{k-1} + k - 2</math> steps. With <math>s_1 = s_2 = 0</math> and <math>s_3 = 0 + (3-2) = 1</math>, and a constant second difference of <math>1</math>, we quickly see that <math>s_k = \binom{k-1}{2}</math>. With the usual convention that <math>\binom{i}{j} = 0</math> for <math>i < j</math>.
+Therefore, if the <math>(k-1)^{\mathrm{st}}</math> student can make <math>s_{k-1}</math> forward steps, the <math>k^{\mathrm{th}}</math> student can make at most <math>s_{k-1} + k - 2</math> steps. With <math>s_1 = s_2 = 0</math> and <math>s_3 = 0 + (3-2) = 1</math>, and a constant second difference of <math>1</math>, we quickly see that <math>s_k = \binom{k-1}{2}</math>.
+With <math>n</math> students in all, the total number of steps is therefore at most <math>\sum_{i=3}^{n}\binom{i-1}{2} = \binom{n}{3}</math>, by the [[Hockey Stick Theorem]]
+==Solution 2==
+WLOG, let <math>h_k=k</math>.  Now, we find the end arrangement with the most switches possible.  We claim that the arrangement will be <math>n,n-1,n-2,\dots ,1</math>, where the left to right direction is the "backwards" direction.  To prove this makes the most switches, we show that there is always at least one more switch that can be done for any other arrangement.  This is elementary to show.  There will always be one height <math>x</math> such that the number to its right is <math>2</math> less than <math>x</math>, unless every number has <math>x-1</math> to the right of <math>x</math> (other than <math>2</math> and <math>1</math>).  The exception occurs at our claim, so our claim is proven.  Now we want to find the maximum ways we can "undo" our arrangement.  But undoing a switch is just doing a switch from our arrangement in the opposite direction.  So, the start arrangement with the most possible switches is the reverse of the end arrangement or <math>1,2,3,\dots ,n</math>.
+We want to find how many switches must be done to get from the start arrangement to the end arrangement.  We start by switching <math>n</math> around until it cannot be switched anymore.  We find that we can switch <math>n</math> <math>n-2</math> times.  When we are switching (or, in other words, moving to the right) the number <math>k</math>, we can switch it <math>k-2</math> times before it is to the left of <math>k-1</math>.  But then we can also switch each of <math>k+1,k+2,\dots ,n</math> (in that order) <math>k-2</math> times before they get stopped again.  Let <math>x=n-k+2</math>.  Then, the sum of the switches is <math>\sum\limits_{x=2}^{n-1} (n-x)(x-1)=\sum\limits_{x=1}^{n} (n-x)(x-1)</math>.
+Rearranging and summing, we get <cmath>\sum\limits_{x=1}^{n} x(n+1)-\sum\limits_{x=1}^{n} n -\sum\limits_{x=1}^{n} x^2=\frac{n(n+1)^2}2-n^2-\frac{n(n+1)(2n+1)}6=\frac{3n(n^2+1)}6-\frac{n(n+1)(2n+1)}6=\frac{n(n^2-3n+2)}6=\frac{n(n-1)(n-2)}{3!}=\binom{n}{3}</cmath>
+==Comment==
+This process of switching is very similar to Bubble Sort, except that the terms must be in consecutive decreasing order, and wraps around <math>2,1,n,n-1\dots</math>. This answer seems to disagree, though, because the worst case efficiency is <math>\mathcal{O}(n^2)</math>, not <math>\mathcal{O}(n^3)</math>.
+https://en.wikipedia.org/wiki/Bubble_sort
-With <math>n</math> students in all, the total number of steps is therefore at most <math>\sum_{i=3}^{n}\binom{n-1}{2} = \binom{n}{3}</math>. The sum is a telescoping sum since: <math>\binom{n}{3} - \binom{n-1}{3} = \binom{n-1}{2}.</math>
+==See also==
+{{USAMO newbox|year=2010|num-b=1|num-a=3}}
+{{MAA Notice}}

2010 USAMO (Problems • Resources)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search