2010 USAMO 第 2 题

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.

有 $n$ 名学生一前一后地站成一圈。学生的身高为 $h_1 < h_2 < \ldots < h_n$。如果身高为 $h_k$ 的学生直接站在身高为 $h_{k-2}$ 或以下的学生后面，则允许两名学生交换位置。证明在到达不可能进行进一步切换的位置之前，不可能进行超过 $\binom{n}{3}$ 这样的切换。