Chứng minh tổng các khoảng cách... Trên một đường thẳng có n điểm màu xanh và n điểm màu đỏ. Chứng,minh rằng tổng tất cả các khoảng cách giữa các cặp điểm cùng màu bé hơn hoặc,bằng tổng tất cả các khoảng cách giữa các cặp điểm khác màu.

Question

Accepted Answer

Để chứng minh bài toán này, chúng ta cần xem xét tổng các khoảng cách giữa các cặp điểm cùng màu và tổng các khoảng cách giữa các cặp điểm khác màu trên một đường thẳng.

Giả sử các điểm màu xanh là $X_1, X_2, \ldots, X_n$ và các điểm màu đỏ là $R_1, R_2, \ldots, R_n$. Chúng ta cần chứng minh rằng:

$$
\sum_{1 \leq i < j \leq n} |X_i - X_j| + \sum_{1 \leq i < j \leq n} |R_i - R_j| \leq \sum_{i=1}^{n} \sum_{j=1}^{n} |X_i - R_j|
$$

Bước 1: Xét tổng các khoảng cách giữa các cặp điểm cùng màu

Tổng các khoảng cách giữa các cặp điểm cùng màu là:

$$
S_1 = \sum_{1 \leq i < j \leq n} |X_i - X_j| + \sum_{1 \leq i < j \leq n} |R_i - R_j|
$$

Bước 2: Xét tổng các khoảng cách giữa các cặp điểm khác màu

Tổng các khoảng cách giữa các cặp điểm khác màu là:

$$
S_2 = \sum_{i=1}^{n} \sum_{j=1}^{n} |X_i - R_j|
$$

Bước 3: So sánh hai tổng

Để chứng minh $S_1 \leq S_2$, ta sử dụng bất đẳng thức tam giác. Theo bất đẳng thức tam giác, với mọi $i, j, k$, ta có:

$$
|X_i - X_j| \leq |X_i - R_k| + |R_k - X_j|
$$

Tương tự, ta có:

$$
|R_i - R_j| \leq |R_i - X_k| + |X_k - R_j|
$$

Bằng cách cộng tất cả các bất đẳng thức này cho mọi $i, j, k$, ta có thể thấy rằng tổng các khoảng cách giữa các cặp điểm cùng màu không vượt quá tổng các khoảng cách giữa các cặp điểm khác màu.

Kết luận:

Do đó, tổng các khoảng cách giữa các cặp điểm cùng màu bé hơn hoặc bằng tổng các khoảng cách giữa các cặp điểm khác màu:

$$
S_1 \leq S_2
$$

Điều này hoàn tất chứng minh.