4

I came across this problem that seems a bit peculiar. Take $$\sum_{1 \leq i < j \leq n} |x_i-x_j|,$$ where $x_1,...,x_n \in [1,35].$ I want to figure out the maximum possible value of this sum in terms of $n$.

To me this, problem could possibly be bounded above by the triangle inequality, but I'm not sure what number I should use for triangulation. We can see that $$\sum_{1 \leq i < j \leq n} |x_i-x_j|,$$ $$\leq \sum_{1 \leq i < k \leq n} |x_i-35|+|x_j-35|,$$ although I am now having some troubles figuring out how this will help me to solve for a meaningful upper bound. Any recommendations?

Celina
  • 43
  • 3

3 Answers3

1

Assume that $1\leq x_1 \leq x_2 \leq \ldots x_n\leq 35$. The sum can then be written:

$$f(x) = \sum_{1\leq i<j\leq n} x_j - x_i = \sum_{i=1}^n (2i-n-1) x_i$$

Let $S$ be the subset of $\mathbb{R}^n$ consisting of all $x$ satisfying $1\leq x_1 \leq x_2 \leq \ldots x_n \leq 35$. The problem amounts to maximizing $f$ over $S$. Note that

$$\frac{\partial f}{\partial x_i} = (2i-n-1),$$

a constant.

Let $x^*$ be a point in $S$ where the maximum is obtained, and let $i$ be an integer such that $x^*_i < x^*_{i+1}$. Clearly, by boundary conditions, we must have $\frac{\partial f}{\partial x_i}\leq0$ and $\frac{\partial f}{\partial x_{i+1}}\geq0$. These conditions can only be satisfied when $i \in \left[ \frac{n-1}{2}, \frac{n+1}{2}\right]$. The boundary conditions then also demand that $x^*_j=1$ for $j<i$ and $x^*_j=35$ for $j>i$. From here it is not difficult to arrive at the solution provided by Solitary of

$$ \begin{cases} \frac{n^2}{4} \times 34 & \text{if $n$ is even}; \\ \frac{n^2 - 1}{4} \times 34 & \text{if $n$ is odd}. \end{cases} $$

dshin
  • 1,525
1

Suppose your sum $S$ is maximized by $x_1,...x_n$ with $x_1\leq x_2\leq ...\leq x_n.$ Then $x_n=35$ otherwise $S$ is increased by changing $x_n$ to $35$. Similarly $x_1=1$. Now if $n>2$ and $x_{n-2} <35$ then changing $x_{n-1}$ to $35$ will either leave $S$ unchanged (which happens when $n=3$) or will increase $S$.So we can put $x_{n-2}=35.$ If $n>3$ a similar argument shows that we can put $x_2=1$. Continuing this up-and-down approach, we reach the configuration suggested by Maffred (comment) and Solitary (answer).There seems to be some discussion about Solitary's answer so I thought to post this to justify his (her) conclusion.

DanielWainfleet
  • 57,985
0

The answer is \begin{cases} \frac{n^2}{4} \times 34 & \text{if $n$ is even}; \\ \frac{n^2 - 1}{4} \times 34 & \text{if $n$ is odd}. \tag{$*$} \end{cases} In words, when $n$ is even, we need to put $\frac{n}{2}$ points at $x = 1$ and put the remaining $\frac{n}{2}$ points at $35$. When $n$ is odd, we put $\frac{n + 1}{2}$ points at $x = 1$ and put the remaining $\frac{n - 1}{2}$ points at $35$. This placement gives the above answer.

To argue why such arrangement is optimal, proceed sequentially. Our goal is to place $\{x_1, \ldots, x_n\}$ so that the sum of distances between to distinct points $S_n$ are maximized. We first need to place $x_1$ and $x_2$ to maximize $|x_1 - x_2|$, clearly, we need to set $x_1 = 1$ and $x_2 = 35$ (or exchange their positions). Now we need to arrange $x_3$, we found that no matter where we place it, it gives the same value of $|x_1 - x_2| + |x_3 - x_1| + |x_3 - x_2| = 34 \times 2$. However, if $n > 3$, we have to put $x_3$ at one of the end points. To see this, the contribution of the newly added point $x_4$ to $S_n$ only depends on $|x_4 - x_3|$, which can be inflated if $x_3 \in (1, 35)$. Therefore, we have to put $x_3$ at one of the end point, and put $x_4$ to another end point to maximize $\sum_{1 \leq i < j \leq 4} |x_i - x_j|$. The procedure can be continued in this manner until we finished placing all $n$ points.

Notice that during the procedure described above, every movement has to be fixed (except for when $n$ is odd, you can put the last point $x_n$ anywhere in $[1, 35]$), that is, you must follow this arrangement (i.e, sequentially put points to opposite end points one after one) to achieve the optimal value. Otherwise, the value of the objective function is always possible to be improved, just as I argued why $x_3$ must be put at one end point.

Zhanxiong
  • 14,040
  • Honestly, I'm not sure if your approach can lead to a solution. Your statements concerning $x_3$ are only true given your particular choice of $x_1$ and $x_2$. Induction can only work if you can generate a claim about $x_3$ that is true regardless of your choice of $x_1$ and $x_2$. – dshin Jan 29 '16 at 04:54
  • To use induction, I only need to show my choice of $(x_1, x_2, x_3)$ gives the desired answer, I didn't see why it doesn't work. I have freedom to choose $x_1, x_2, \ldots, x_n$ at any stage. – Zhanxiong Jan 29 '16 at 05:01
  • You have the freedom to choose them as you wish; to prove that your choice optimizes the given sum, $S_n$, though, is a different story. To say, "this choice of $x_n$ provably maximizes the sum if $x_1, \ldots, x_{n-1}$ are chosen to minimize the sum $S_{n-1}$", doesn't do much for your cause. – dshin Jan 29 '16 at 05:07
  • Hmm, maybe I should not say use induction but just justify the procedure I described in my solution. I will add more details. – Zhanxiong Jan 29 '16 at 05:11