Math Labs

Bài 1

Cho các số thực x1≥x2≥⋯≥xnx_1 \ge x_2 \ge \cdots \ge x_n và y1≥y2≥⋯≥yny_1 \ge y_2 \ge \cdots \ge y_n. Chứng minh rằng nếu z1,z2,…,znz_1, z_2, \ldots, z_n là một hoán vị bất kỳ của y1,y2,…,yny_1, y_2, \ldots, y_n thì ∑i=1n(xi−yi)2≤∑i=1n(xi−zi)2\sum_{i=1}^{n} (x_i - y_i)^2 \le \sum_{i=1}^{n} (x_i - z_i)^2.
Bước 1 trên 5: Bất đẳng thức cần chứng minh nói gì
Bước trướcBước tiếp
Hiểu nôm na

Hãy hình dung xix_i là nn chỗ đỗ xe cố định trên một trục số, còn yiy_i là nn chiếc xe cần đỗ vào đó theo một thứ tự nào đó. Ghép chiếc xe lớn nhất với chỗ lớn nhất, chiếc lớn nhì với chỗ lớn nhì, cứ thế (cách ghép "đã sắp thứ tự" yiy_i) giữ cho mọi xe gần chỗ của nó nhất có thể. Xáo trộn các xe theo bất kỳ thứ tự nào khác ziz_i chỉ có thể làm tổng bình phương khoảng cách đỗ xe tăng lên, không bao giờ giảm. Bài toán yêu cầu chứng minh chặt chẽ trực giác đó.

∑i=1n(xi−yi)2≤∑i=1n(xi−zi)2\sum_{i=1}^n (x_i-y_i)^2 \le \sum_{i=1}^n (x_i-z_i)^2
Phân tích chi tiết

Hai vế của bất đẳng thức đều là tổng của nn bình phương hiệu giữa dãy cố định xix_i và một dãy lấy từ cùng đa tập hợp {y1,…,yn}\{y_1, \ldots, y_n\}: ở vế trái dãy đó đã được sắp cùng thứ tự với xx, ở vế phải là một hoán vị zz bất kỳ. Khẳng định là cách ghép đã sắp thứ tự làm cho tổng bình phương hiệu nhỏ nhất trong số n!n! cách ghép có thể.