Maths Olympiad Prep

Library / /517 of 520

Combinatorics Difficulty 4.9 AIME Prove it

There are nn students standing in a circle, one behind the
other. The students have heights h1<h2<<hnh_1 < h_2 < \ldots < h_n. If a
student with height hkh_k is standing directly behind a student
with height hk2h_{k-2} or less, the two students are permitted to
switch places. Prove that it is not possible to make more than
(n3)\binom{n}{3} such switches before reaching a position in which
no further switches are possible.

Solution

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

(00)=1,(nk)=(n1k)+(n1k1)\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 h1h_1 and h2h_2 are always stationary, while other students potentially move past them.
For k>2k > 2, the student with height hkh_k can never switch places with the student with height hk1h_{k-1}, and the former can make at most k2k-2 more forward moves than the latter (when all the students of heights h1,hk2h_1, \ldots h_{k-2} are between hkh_k and hk1h_{k-1} in the forward direction).
Therefore, if the (k1)st(k-1)^{\mathrm{st}} student can make sk1s_{k-1} forward steps, the kthk^{\mathrm{th}} student can make at most sk1+k2s_{k-1} + k - 2 steps. With s1=s2=0s_1 = s_2 = 0 and s3=0+(32)=1s_3 = 0 + (3-2) = 1, and a constant second difference of 11, we quickly see that sk=(k12)s_k = \binom{k-1}{2}.
With nn students in all, the total number of steps is therefore at most i=3n(i12)=(n3)\sum_{i=3}^{n}\binom{i-1}{2} = \binom{n}{3}. The sum is a telescoping sum since: (n3)(n13)=(n12).\binom{n}{3} - \binom{n-1}{3} = \binom{n-1}{2}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.