1

If $x_{1},x_{2},x_{3},\cdots \cdots , x_{n}$ be real numbers between $0$ to $1$. Then the greatest value of $\displaystyle \mathop{\sum}_{1\leq i<j\leq n} \bigg|x_{i}-x_{j}\bigg|$ is

what i try

$\displaystyle \mathop{\sum}_{1\leq i<j\leq n}\bigg|x_{i}-x_{j}\bigg|=\bigg|x_{1}-x_{2}\bigg|+\bigg|x_{1}-x_{3}\bigg|+\cdots \bigg|x_{1}-x_{n}\bigg|+\bigg|x_{2}-x_{3}\bigg|+\cdots +\bigg|x_{n-1}-x_{n}\bigg|$

i am trying using triangle inequality,

$\displaystyle \bigg|x_{1}-x_{2}\bigg|+\bigg|x_{2}-x_{3}\bigg|+\cdots +\bigg|x_{n-1}-x_{n}\bigg|\geq \bigg|x_{1}-x_{n}\bigg|$

how do i solve it help me please

jacky
  • 5,194

1 Answers1

5

Notice that the function $f(\mathbf{x})=\sum_{i<j}|{x_i-x_j}|$ is convex, as a sum of convex functions (the absolute value of a linear form is convex). You are trying to maximize $f$ on the cube $[0,1]^{n}$. Since $f$ is convex, there is a vertex of this cube that is a maximizer. The value at a vertex is $|A|(n-|A|)$, where $A$ is the set of coordinates having a $1$. Maximizing over $|A|$ gives $|A|=n/2$ (if $n$ is even), and the greatest value is $n^2/4$, or $|A|=(n-1)/2$ (if $n$ is odd) and the greatest value is $(n-1)(n+1)/4$.

Pierre
  • 352