Câu hỏi 49
Trong một thành phố có $n \geqslant 3$ hòn đảo. Ban đầu, công ty phà mở một số 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ó hai đảo nào thuộc hai nhóm khác nhau được nối với nhau bằng một tuyến phà.
Sau mỗi năm, công ty phà sẽ đóng một tuyến phà giữa hai đảo $X$ và $Y$ nào đó. Đồng thời, để duy trì dịch vụ, công ty sẽ mở các tuyến mới theo quy tắc sau: với mỗi đảo được nối bằng tuyến phà với đúng một trong hai đảo $X$ và $Y$, một tuyến mới giữa đảo đó và đảo còn lại trong hai đảo $X$, $Y$ sẽ được thêm vào.
Giả sử tại mọi thời điểm, nếu ta chia tất cả các đảo thành hai nhóm khác rỗng theo cách bất kỳ, thì biết rằng sau một số năm công ty phà sẽ đóng một tuyến nối hai đảo thuộc hai nhóm đó. Chứng minh rằng sau một số năm sẽ có một đảo được nối với tất cả các đảo còn lại bằng các tuyến phà.
Sau mỗi năm, công ty phà sẽ đóng một tuyến phà giữa hai đảo $X$ và $Y$ nào đó. Đồng thời, để duy trì dịch vụ, công ty sẽ mở các tuyến mới theo quy tắc sau: với mỗi đảo được nối bằng tuyến phà với đúng một trong hai đảo $X$ và $Y$, một tuyến mới giữa đảo đó và đảo còn lại trong hai đảo $X$, $Y$ sẽ được thêm vào.
Giả sử tại mọi thời điểm, nếu ta chia tất cả các đảo thành hai nhóm khác rỗng theo cách bất kỳ, thì biết rằng sau một số năm công ty phà sẽ đóng một tuyến nối hai đảo thuộc hai nhóm đó. Chứng minh rằng sau một số năm sẽ có một đảo được nối với tất cả các đảo còn lại bằng các tuyến phà.