MathDB
'10 USAMO #2: Students in a Circle

Source:

April 29, 2010
USA(J)MOUSAMOinductionmonovariantUSAMTS

Problem Statement

There are nn students standing in a circle, one behind the other. The students have heights h1<h2<⋯<hnh_1<h_2<\dots <h_n. If a student with height hkh_k is standing directly behind a student with height hk−2h_{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.
Back to ProblemsView on AoPS