Câu hỏi 7
Ở Lineland có $n \geqslant 1$ thị trấn dọc một con đường từ trái sang phải. Mỗi thị trấn có một xe ủi trái đặt bên trái, hướng sang trái, và một xe ủi phải đặt bên phải, hướng sang phải. Kích thước $2 n$ xe khác nhau. Khi một xe hướng phải đối đầu một xe hướng trái, xe lớn đẩy xe nhỏ khỏi đường. Tuy nhiên phía sau các xe không được bảo vệ: nếu một xe đến phía sau xe khác, xe thứ nhất đẩy xe thứ hai khỏi đường bất kể kích thước.
Cho hai thị trấn $A$, $B$, với $B$ bên phải $A$. Nói $A$ có thể quét sạch $B$ nếu xe ủi phải của $A$ đi tới $B$, đẩy khỏi đường mọi xe nó gặp. Tương tự, $B$ quét sạch $A$ nếu xe ủi trái của $B$ tới $A$, đẩy mọi xe của các thị trấn trên đường khỏi đường.
Chứng minh có đúng một thị trấn không thể bị thị trấn nào khác quét sạch.
Cho hai thị trấn $A$, $B$, với $B$ bên phải $A$. Nói $A$ có thể quét sạch $B$ nếu xe ủi phải của $A$ đi tới $B$, đẩy khỏi đường mọi xe nó gặp. Tương tự, $B$ quét sạch $A$ nếu xe ủi trái của $B$ tới $A$, đẩy mọi xe của các thị trấn trên đường khỏi đường.
Chứng minh có đúng một thị trấn không thể bị thị trấn nào khác quét sạch.