Câu hỏi 30
Cho $n$ là một số nguyên dương. Có $n$ hòn đảo được nối với nhau bởi $n - 1$ cây cầu sao cho có thể đi từ một hòn đảo bất kì đến một hòn đảo bất kì khác. Một buổi chiều, một đám cháy bùng lên ở một trong các hòn đảo. Mỗi buổi sáng, đám cháy lan sang tất cả các hòn đảo kề. (Hai hòn đảo được gọi là kề nhau nếu chúng được nối bởi một cây cầu.) Để kiểm soát sự lan rộng, mỗi đêm người ta phá hủy một cây cầu cho đến khi đám cháy không còn chỗ nào để lan sang vào ngày hôm sau. Gọi $X$ là số cây cầu nhỏ nhất có thể phải phá hủy trước khi đám cháy ngừng lan. Tìm giá trị lớn nhất có thể của $X$ trên mọi cấu hình của các cây cầu và các hòn đảo cùng với vị trí hòn đảo nơi đám cháy bắt đầu.