Câu hỏi 75
Một quốc gia muốn nối $2021$ thành phố bằng các tuyến bay luôn có hai chiều, theo các yêu cầu sau:
- Giữa hai thành phố bất kỳ, có thể đi lại bằng một chuyến bay trực tiếp hoặc bằng một dãy chuyến bay nối tiếp.
- Với mỗi cặp thành phố $(A,B)$ có chuyến bay trực tiếp, tồn tại một thành phố khác $C$ sao cho cả $(A,C)$ và $(B,C)$ đều có chuyến bay trực tiếp.
Chứng minh rằng cần ít nhất $3030$ tuyến bay để đáp ứng hai yêu cầu này.
- Giữa hai thành phố bất kỳ, có thể đi lại bằng một chuyến bay trực tiếp hoặc bằng một dãy chuyến bay nối tiếp.
- Với mỗi cặp thành phố $(A,B)$ có chuyến bay trực tiếp, tồn tại một thành phố khác $C$ sao cho cả $(A,C)$ và $(B,C)$ đều có chuyến bay trực tiếp.
Chứng minh rằng cần ít nhất $3030$ tuyến bay để đáp ứng hai yêu cầu này.