Finding an Upper Bound on This Inequality 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?
 A: 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}
$$
A: 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.
A: 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. 
