Maths Olympiad Prep

Library / /3 of 32

Algebra Difficulty 4.7 AIME Prove it Romania

Let nn be a positive integer and let x1,x2,…,xnx_1, x_2, \dots, x_n and y1,y2,…,yny_1, y_2, \dots, y_n be real numbers. Prove that there exists a number ii, i=1,2,…,ni = 1, 2, \dots, n, such that
∑j=1n∣xi−xj∣≤∑j=1n∣xi−yj∣. \sum_{j=1}^{n} |x_i - x_j| \le \sum_{j=1}^{n} |x_i - y_j|.

Solution

Without the loss of generality, suppose x1≤x2≤⋯≤xnx_1 \le x_2 \le \dots \le x_n. For each k=1,2,…,nk = 1, 2, \dots, n we have ∣x1−xk∣+∣xn−xk∣=∣x1−xn∣≤∣x1−yk∣+∣xn−yk∣|x_1 - x_k| + |x_n - x_k| = |x_1 - x_n| \le |x_1 - y_k| + |x_n - y_k|, hence
∑k=1n∣x1−xk∣+∑k=1n∣xn−xk∣≤∑k=1n∣x1−yk∣+∑k=1n∣xn−yk∣. \sum_{k=1}^{n} |x_1 - x_k| + \sum_{k=1}^{n} |x_n - x_k| \le \sum_{k=1}^{n} |x_1 - y_k| + \sum_{k=1}^{n} |x_n - y_k|.
The claim holds for i=1i = 1 or i=ni = n.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.