27. (POL 2) Determine the maximum value of the sum  
$$ \sum_{i<j} x_{i} x_{j}\left(x_{i}+x_{j}\right) $$  
over all $n$-tuples $\left(x_{1}, \ldots, x_{n}\right)$, satisfying $x_{i} \geq 0$ and $\sum_{i=1}^{n} x_{i}=1$.
27. Write $F\left(x_{1}, \ldots, x_{n}\right)=\sum_{i<j} x_{i} x_{j}$, where $x_{i} \geq 0$ and $\sum_{i=1}^{n} x_{i}=1$. We want to find the maximum value of $F$.

To do this, we will show that if $x_{k-1}, x_{k}, x_{k+1}$ are all positive, then we can increase $F$ by setting $x_{k}=0$ and increasing $x_{k-1}$ and $x_{k+1}$ appropriately. Specifically, we can set $x_{k-1}^{\prime}=x_{k-1}+x_{k}$ and $x_{k+1}^{\prime}=x_{k+1}+x_{k}$, and $x_{i}^{\prime}=x_{i}$ for all other $i$. The new value of $F$ will be:
$$
F\left(x_{1}^{\prime}, \ldots, x_{n}^{\prime}\right) = F\left(x_{1}, \ldots, x_{n}\right) + x_{k}\left(x_{k-1}+x_{k+1}-x_{k}\right) > F\left(x_{1}, \ldots, x_{n}\right)
$$
because $x_{k-1}+x_{k} \leq \frac{2}{3}\left(x_{1}+x_{k-1}+x_{k-2}\right) \leq \frac{2}{3}$. Repeating this procedure we can reduce the number of nonzero $x_{i}$'s to two, increasing the value of $F$ in each step. It remains to maximize $F$ over $n$-tuples $\left(x_{1}, x_{2}, 0, \ldots, 0\right)$ with $x_{1}, x_{2} \geq 0, x_{1}+x_{2}=1$: in this case $F$ equals $x_{1} x_{2}$ and attains its maximum value $\frac{1}{4}$ when $x_{1}=x_{2}=\frac{1}{2}, x_{3}=\ldots, x_{n}=0$.