MathNet 2015-part-03 — 191 bài (EN–VI) Câu hỏi 76

Ở xứ Lineland có $n \geqslant 1$ thị trấn nằm dọc theo một con đường chạy từ trái sang phải. Mỗi thị trấn có một xe ủi trái (đặt ở bên trái thị trấn và hướng sang trái) và một xe ủi phải (đặt ở bên phải thị trấn và hướng sang phải). Kích thước của $2n$ chiếc xe ủi đôi một khác nhau. Mỗi khi một xe ủi phải và một xe ủi trái đối đầu nhau, xe ủi lớn hơn sẽ đẩy xe ủi nhỏ hơn ra khỏi đường. Mặt khác, các xe ủi khá yếu ở phía sau; vì vậy, nếu một xe ủi chạm tới phía sau của một xe ủi khác thì xe thứ nhất đẩy xe thứ hai ra khỏi đường, bất kể kích thước của chúng.
Gọi $A$ và $B$ là hai thị trấn, với $B$ nằm bên phải $A$. Ta nói thị trấn $A$ có thể quét sạch thị trấn $B$ nếu xe ủi phải của $A$ có thể di chuyển tới $B$ và đẩy khỏi đường mọi xe ủi mà nó gặp. Tương tự, $B$ có thể quét sạch $A$ nếu xe ủi trái của $B$ có thể di chuyển tới $A$ và đẩy khỏi đường mọi xe ủi của mọi thị trấn trên đường đi.
Chứng minh rằng có đúng một thị trấn không bị thị trấn nào khác quét sạch.