Câu hỏi 144
Có $n$ hòn đảo, với $n \ge 3$. Một công ty phà mở tuyến giữa một số cặp đảo sao cho mỗi khi ta chia các đảo thành hai nhóm khác rỗng, ta luôn tìm được ở mỗi nhóm một đảo sao cho giữa hai đảo này có tuyến phà. Cuối mỗi năm, công ty chọn hai đảo $X$ và $Y$ có tuyến nối với nhau và đóng tuyến giữa chúng. Đồng thời, với mọi đảo $A$ khác: nếu $A$ có tuyến tới $X$ nhưng không có tuyến tới $Y$ thì công ty mở thêm tuyến giữa $A$ và $Y$; ngược lại, nếu $A$ có tuyến tới $Y$ nhưng không có tuyến tới $X$ thì công ty mở thêm tuyến giữa $A$ và $X$.
Với hai nhóm đảo $\mathcal{A}$ và $\mathcal{B}$, nếu $A \in \mathcal{A}$ và $B \in \mathcal{B}$, ta nói tuyến nối $A$ và $B$ kết nối $\mathcal{A}$ và $\mathcal{B}$. Giả sử ta biết rằng tại mọi thời điểm, nếu chia các đảo thành hai nhóm khác rỗng thì công ty chắc chắn sẽ đóng một tuyến kết nối hai nhóm này trong vòng một số năm. Chứng minh rằng sau một số năm sẽ có một hòn đảo có tuyến tới tất cả các đảo còn lại.
Với hai nhóm đảo $\mathcal{A}$ và $\mathcal{B}$, nếu $A \in \mathcal{A}$ và $B \in \mathcal{B}$, ta nói tuyến nối $A$ và $B$ kết nối $\mathcal{A}$ và $\mathcal{B}$. Giả sử ta biết rằng tại mọi thời điểm, nếu chia các đảo thành hai nhóm khác rỗng thì công ty chắc chắn sẽ đóng một tuyến kết nối hai nhóm này trong vòng một số năm. Chứng minh rằng sau một số năm sẽ có một hòn đảo có tuyến tới tất cả các đảo còn lại.