USAMO 2010 — Ngày 1 và Ngày 2 Câu hỏi 2

Có $n$ học sinh đứng thành một vòng tròn, người sau nối tiếp người trước. Chiều cao của họ là $h_1\lt h_2\lt \cdots\lt h_n$. Nếu người cao $h_k$ đứng ngay sau một người cao không quá $h_{k-2}$ thì hai người được phép đổi chỗ. Chứng minh không thể thực hiện quá $\binom n3$ lần đổi chỗ như vậy trước khi đến một vị trí không còn phép đổi nào hợp lệ.

Tác giả đề bài: David Speyer (theo ghi nhận trong tài liệu lời giải bên thứ ba).