Câu hỏi 14
Một thành phố có $n \geqslant 3$ đảo. Ban đầu, công ty phà cung cấp tuyến giữa một số cặp đảo sao cho không thể chia các đảo thành hai nhóm mà không có tuyến phà nối hai đảo khác nhóm.
Sau mỗi năm, công ty đóng tuyến giữa hai đảo $X$, $Y$. Đồng thời, với mỗi đảo đang có tuyến nối đúng một trong $X$, $Y$, công ty mở tuyến nối đảo ấy với đảo còn lại trong $X$, $Y$.
Giả sử tại mọi thời điểm, khi chia các đảo thành hai nhóm không rỗng theo bất kỳ cách nào, một tuyến nối hai đảo khác nhóm sẽ bị đóng sau một số năm. Chứng minh sau một số năm có một đảo có tuyến phà nối với tất cả đảo khác.
Sau mỗi năm, công ty đóng tuyến giữa hai đảo $X$, $Y$. Đồng thời, với mỗi đảo đang có tuyến nối đúng một trong $X$, $Y$, công ty mở tuyến nối đảo ấy với đảo còn lại trong $X$, $Y$.
Giả sử tại mọi thời điểm, khi chia các đảo thành hai nhóm không rỗng theo bất kỳ cách nào, một tuyến nối hai đảo khác nhóm sẽ bị đóng sau một số năm. Chứng minh sau một số năm có một đảo có tuyến phà nối với tất cả đảo khác.