Câu hỏi 159
Đất nước "U" có các thành phố $A_1, A_2, \dots, A_n$. Chúng được nối với nhau bởi các chuyến bay sao cho có thể đi từ một thành phố bất kỳ đến một thành phố bất kỳ khác (có thể quá cảnh). Gọi $d_{i,j}$ là số chuyến bay ít nhất cần thiết để đi từ thành phố $A_i$ đến thành phố $A_j$, gọi $d$ là tổng số chuyến bay ở đất nước "U" và đặt
$$
D = d_{1,1} + d_{1,2} + \dots + d_{1,n} + d_{2,3} + d_{2,4} + \dots + d_{2,n} + \dots + d_{n-1,n}.
$$
Chứng minh rằng:
$$
d + \frac{D}{n-1} \le \frac{1}{2}(n+1)(n+2).
$$
$$
D = d_{1,1} + d_{1,2} + \dots + d_{1,n} + d_{2,3} + d_{2,4} + \dots + d_{2,n} + \dots + d_{n-1,n}.
$$
Chứng minh rằng:
$$
d + \frac{D}{n-1} \le \frac{1}{2}(n+1)(n+2).
$$