1
$\begingroup$

Let $a_1,...,a_n$ be arbitary integers and suppose $b_1,b_2,...,b_n$ is a permutation of $a_i's.$ Then the value of $|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|$ is

A. is less than or equal to $n$,

B. can be any arbitary positive integers,

C. can be any non-negative integer,

D. must be zero

My solution is:

We have, $|(a_1+...+a_n)-(b_1+b_2+...+b_n)|\leq |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|$ (from Triangle inequality). But, $|(a_1+...+a_n)-(b_1+b_2+...+b_n)|=0\leq |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|.$ This implies that $|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|$ can be any non-negative integer. So, we can easily, eliminate option $B$(as if the two permutations of $a_i$ and $b_i$ are equal, then, $|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|=0$) and $D.$ Option $D,$ can be eliminated by considering the two permutations $(a_1,a_2,...,a_{10})=(1,2,...,10)$ and $(b_1,b_2,...,b_{10})=(10,9,...,1)$ , then $|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\gt 10.$ So, the only option remaining is $C.$

Is the answer found out, correct?

$\endgroup$
0

1 Answer 1

0
$\begingroup$

You have not eliminated answer choice (A), but this is trivial. Consider $$ a_i = \begin{cases} 0, & i < n \\ 2n, & i = n \end{cases}$$ with $b_i \ne a_i$ for each $i$. Then the sum in question is certainly bigger than $n$.


We have, $|(a_1+...+a_n)-(b_1+b_2+...+b_n)|\leq |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|$ (from Triangle inequality). But, $|(a_1+...+a_n)-(b_1+b_2+...+b_n)|=0\leq |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|.$

You do not need the triangle inequality to conclude this. The absolute value of a quantity is nonnegative, and the sum of nonnegative quantities certainly is too.


This implies that $|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|$ can be any non-negative integer.

It doesn't, actually. All it tells you is a lower bound; but how do you know if it is the best lower bound? How do you know if each nonnegative integer can, in fact, be reached? All you know is that you certainly cannot achieve negative values.

So really, you haven't found out anything of value by this point in the problem, since none of the options are concerned with negative integers in the first place. It is only after here you develop ideas of substance for the problem at hand.


Otherwise, you're right. Answer choices (B) and (D) are easily eliminated by example: for instance, $n$ distinct numbers, under the identity and any non-identity permutation respectively. (C) is the only remaining answer.

Of course, one should always ask themselves whether (C) is also correct; who knows, maybe the prompt is incorrect, perhaps the author made an error. I would argue, as phrased, (C) is wrong too.

Consider $a_1 = 1$ and $a_2 = 2$, for the $n=2$ case. Is it ever possible for one to achieve, say, $\sum_i |a_i - b_i| = 3$, even if one permutes the $a_i$ around in different ways? The only way to achieve this would be to change the numbers involved (be it the $a_i$ or even the number of $a_i$ there are, $n$).

Most likely, the intended phrasing was "the sum lies in the nonnegative integers", not that every nonnegative integer can be achieved, since the question (in my reading) fixes the $n$, the $a_i$, and the $b_i$, before making a conjecture as to the value.

Now, of course, an alternative reading -- we can find, given an $s \in \mathbb{Z}_{\ge 0}$ to achieve, an $n$, some $a_i$, and corresponding $b_i$ such that $\sum_i |a_i - b_i| = s$ -- certainly is true, and trivial to construct examples for.

This is a lesson I feel is important, if probably entirely unnecessary for the scope of your particular problem and likely not a detail you were intended to fret over.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .