Question

Trong một quốc gia gồm \(n\ge2\)thành phố. Giữa hai thành phố bất kì có đường bay trực tiếp theo hai chiều. Người ta muốn cấp phép khai thác cho các đường bay cho một hãng hàng không với các điều kiện sau đây:

1/ Mỗi đường bay chỉ được cấp phép cho một hãng hàng không duy nhất.

2/ Di chuyển đường bay của một hãng hàng không tùy ý, người ta có thể đi từ thành phố bất kỳ tới các thành phố còn lại.

Hỏi có thể cấp phép tối đa cho bao nhiêu hãng hàng không?

Answer 1

Từ 1 thành phố bất kì ta cần n - 1 đường bay nối đến n - 1 thành phố còn lại

Vậy từ n thành phố cần \(n\left(n-1\right)\)đường bay

Mà với cách tính này thì số đường bay bị gấp lên 2 lần

Vậy số đường cần là : \(\frac{n\left(n-1\right)}{2}\)

Vậy có thể cấp phép tối đa cho cho \(\frac{n\left(n-1\right)}{2}\)hãng hàng không .