Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(Created page with '==Problem== There are <math>n</math> students is 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 he…')
 
(→‎Solution)
Line 9: Line 9:
  
 
==Solution==
 
==Solution==
 +
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 anti-clockwise). We'll call this direction <i>forward</i>.
 
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>.
  
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).
 
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{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>
 
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>

Revision as of 12:01, 11 May 2010

Problem

There are $n$ students is 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

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 anti-clockwise). 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{n-1}{2} = \binom{n}{3}$. The sum is a telescoping sum since: $\binom{n}{3} - \binom{n-1}{3} = \binom{n-1}{2}.$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_USAMO_Problems/Problem_2&oldid=34481"