Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we have two sets of data, $X$ and $Y$, each of which contains $10$ positive numbers. Now let us order the data sets $X=\left\{ x_{1},\cdots,x_{10}\right\}$, $x_{1}\ge\cdots\ge x_{10}>0$ and $Y=\left\{ y_{1},\cdots,y_{10}\right\}$, $y_{1}\ge\cdots\ge y_{10}>0$ and define $d:=\sum_{k=1}^{10}\left|x_{i_{k}}-y_{j_{k}}\right|$, that is the sum of the distances of the numbers in pairs from the two data sets. Does anyone know how to prove that $d$ achieves its minimum when $i_{k}=j_{k}=k$ for $1\le k\le10$, or is there any counter example if it is not true? Thanks.

share|improve this question
1  
How are $i_k$ and $j_k$ defined? Do you already have some ordering for $X$ and $Y$ and then assign a new one to them? –  Alex Becker Jan 1 '12 at 8:27
    
@Alex. ${i_1,\cdots,i_{10}}$ is a permutation of ${1, 2, \cdots, 10}$, similarly for ${j_1,\cdots,j_{10}}$. –  098 Jan 1 '12 at 8:34
    
Have you tried applying the triangle inequality ($|a+b|\leq |a|+|b|$)? –  Alex Becker Jan 1 '12 at 8:38
    
@Alex. Yes, I have tried that. But I couldn't prove or disprove it. –  098 Jan 1 '12 at 8:56
add comment

1 Answer

Lets consider the example of two sets, $X_2$ and $Y_2$, each of which have two elements which satisfy $x_1\geq x_2\geq 0, y_1\geq y_2\geq 0$. Then $$d=\sum_{k=1}^{2}\left|x_{i_{k}}-y_{j_{k}}\right| = |x_{i_1}-y_{j_1}|+|x_{i_2}-y_{j_2}|$$ and to determine all possible values we have only two cases to check, one where $i_k=j_k, k\in \{1,2\}$ and the other in which $i_k\neq j_k, k\in \{1,2\}$. In the first case, $d = |x_1 - y_1| + |x_2 - y_2|$, and in the second case $d = |x_1 - y_2| + |x_2 - y_1|$, which we break down into two further cases: $x_1 \geq y_1$ and $x_1\leq y_1$. In the first case $$|x_1 - y_2| + |x_2 - y_1| = |x_1 - y_1| + |y_1-y_2| + |x_2 - y_1|\geq |x_1 - y_1|+|x_2-y_2|$$ while in the second we have $x_2\leq x_1\leq y_1$ so $$|x_1 - y_2| + |x_2 - y_1| = |x_1 - y_2| + |x_1 - y_1| + |x_2 - x_1|\geq |x_1 - y_1|+|x_2-y_2|$$ with the inequality in both cases coming from the triangle inequality. Certainly, this method of case-by-case analysis is too laborious to use directly for your problem. However, the case of two elements turns out to be the crucial one in order to apply induction, which proves the theorem for any number of elements. The key observation is that the above proof can be modified to show that $$d=\sum_{k=1}^{n}\left|x_{i_{k}}-y_{j_{k}}\right| = |x_{i_1}-y_{j_1}|+\sum_{k=2}^{n}\left|x_{i_k}-y_{j_k}\right|$$ is at least the result of using some permutation such that $i_1=j_1$. I leave the details of this to you.

share|improve this answer
    
This works fine for the case where there are two elements in the set. But, the induction step is not straight-forward. Only 2 possible cases here are $x_1\le y_1$ and vice versa. But as the number of elements increases, this breakdown alone will not be sufficient in my opinion. –  Nikhil Bellarykar Jan 1 '12 at 9:38
    
@NikhilBellarykar Inductive case: In the case where $x_{i_k}=y_{j_k}$ for some $k$, we are done. Otherwise, we have some permutation $x_{i_k'}$ such that $x_{i_k'}=x_{i_k}$ for all but two values of $k$ and for one of these values of $k$, $x_{i_k'}=y_{j_k}$. –  Alex Becker Jan 1 '12 at 9:45
1  
hmm got the idea somewhat. thanks. –  Nikhil Bellarykar Jan 1 '12 at 17:48
    
@Alex. Did you mean $i_k=j_k$ in your comment? How would you do by induction about the case $|x_1-y_2|+\cdots+|x_9-y_{10}|+|x_{10}-y_1|$? Thanks! –  098 Jan 2 '12 at 8:24
    
@098 Yes I did, sorry. In that case I would switch $y_2$ and $y_1$ to get $|x_1-y_1|+9$ terms, which cannot increase the value of $d$ by a similar proof as the one I gave for the $n=2$ case, with $x_{10}$ substituted for $x_2$. –  Alex Becker Jan 2 '12 at 8:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.