Câu hỏi 122
Một tập gồm $n$ điểm trong không gian Euclid 3 chiều, không có bốn điểm nào đồng phẳng, được chia thành hai tập con $A$ và $B$. Một $\mathcal{A}\mathcal{B}$-cây là một cấu hình gồm $n-1$ đoạn thẳng, mỗi đoạn có một đầu mút thuộc $A$ và đầu mút kia thuộc $B$, sao cho các đoạn không tạo thành đường gấp khúc kín. Một $\mathcal{A}\mathcal{B}$-cây được biến đổi thành một cây khác như sau: chọn ba đoạn thẳng phân biệt $A_1B_1$, $B_1A_2$ và $A_2B_2$ của $\mathcal{A}\mathcal{B}$-cây sao cho $A_1$ thuộc $A$ và $A_1B_1 + A_2B_2 \gt A_1B_2 + A_2B_1$, rồi bỏ đoạn $A_1B_1$ và thay bằng đoạn $A_1B_2$. Cho một $\mathcal{A}\mathcal{B}$-cây bất kỳ, chứng minh rằng mọi dãy các phép biến đổi liên tiếp đều kết thúc (không thể thực hiện thêm phép biến đổi nào) sau hữu hạn bước.