Câu hỏi 24
Ở Rectilandia có $n$ thành phố nằm dọc theo một con đường thẳng. Mỗi thành phố được giao hai robot: một R-robot, đặt ở bên phải thành phố và chỉ di chuyển theo hướng đó (sang phải), và một L-robot, đặt ở bên trái thành phố và chỉ di chuyển theo hướng đó (sang trái). Mỗi robot trong $2n$ robot được gán một số, và $2n$ số này đôi một khác nhau. Hai robot đối đầu nhau theo các quy tắc sau:
* Nếu một L-robot gặp một R-robot thì robot có số lớn hơn thắng, còn robot có số nhỏ hơn rời khỏi con đường.
* Các robot rất dễ bị tấn công từ phía sau, nên nếu hai R-robot gặp nhau mà giữa chúng không có robot nào khác thì robot ở bên phải rời khỏi con đường. Tương tự, nếu hai L-robot gặp nhau thì robot ở bên trái rời khỏi con đường; trong cả hai trường hợp, điều này xảy ra bất kể các số được gán cho chúng.
Giả sử các thành phố $A$ và $B$ nằm trên con đường theo thứ tự đó: $B$ ở bên phải $A$. Ta nói $A$ thắng $B$ nếu R-robot của $A$ có thể tiến về phía $B$ và loại bỏ mọi robot nó gặp trên đường đi. Tương tự, ta nói $B$ thắng $A$ nếu L-robot của $B$ có thể tiến về phía $A$ và loại bỏ mọi robot nó gặp trên đường đi. Chứng minh rằng tồn tại duy nhất một thành phố không thể bị bất kỳ thành phố nào khác thắng.
* Nếu một L-robot gặp một R-robot thì robot có số lớn hơn thắng, còn robot có số nhỏ hơn rời khỏi con đường.
* Các robot rất dễ bị tấn công từ phía sau, nên nếu hai R-robot gặp nhau mà giữa chúng không có robot nào khác thì robot ở bên phải rời khỏi con đường. Tương tự, nếu hai L-robot gặp nhau thì robot ở bên trái rời khỏi con đường; trong cả hai trường hợp, điều này xảy ra bất kể các số được gán cho chúng.
Giả sử các thành phố $A$ và $B$ nằm trên con đường theo thứ tự đó: $B$ ở bên phải $A$. Ta nói $A$ thắng $B$ nếu R-robot của $A$ có thể tiến về phía $B$ và loại bỏ mọi robot nó gặp trên đường đi. Tương tự, ta nói $B$ thắng $A$ nếu L-robot của $B$ có thể tiến về phía $A$ và loại bỏ mọi robot nó gặp trên đường đi. Chứng minh rằng tồn tại duy nhất một thành phố không thể bị bất kỳ thành phố nào khác thắng.