MathDB

Problem 2

Part of 2017 Pakistan TST

Problems(1)

Switching students in a circle, due to height.

Source: Pakistan TST (2) 2017. P2

1/28/2017
There are nn students in a circle, one behind the other, all facing clockwise. The students have heights h1<h2<h3<⋯<hnh_1 <h_2 < h_3 < \cdots < h_n. If a student with height hkh_k is standing directly behind a student with height hk−2h_{k-2} or lesss, 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.
combinatoricsalgorithm