Maximize $x_1x_2+x_2x_3+\cdots+x_nx_1$ Let $x_1,x_2,\ldots,x_n$ be $n$ non-negative numbers ($n&gt;2$) with a fixed sum $S$.
What is the maximum of $x_1x_2+x_2x_3+\cdots+x_nx_1$?
Fixed This is carlop's solution simplifyid, so please upvote that solution.

For $n=3$ we have by C-S or rearrangement 

$$x_1x_2+x_2x_3+x_3x_1 \leq x_1^2+x_2^2+x_3^2$$

Adding $2(x_1x_2+x_2x_2+x_3x_1)$ we get

$$3(x_1x_2+x_2x_3+x_3x_1) \leq (x_1+x_2+x_3)^2 \,.$$

For $n \geq 4$ even we have

$$x_1x_2+x_2x_3+....+x_{2k}x_1 \leq (x_1+x_3+..+x_{2k} )( x_2+x_4+...+x_{2k-1})$$

since any term on the LHS appears on the RHS.

Thus

$$\sqrt{x_1x_2+x_2x_3+....+x_{2k}x_1} \leq \frac{x_1+x_3+..+x_{2k} + x_2+x_4+...+x_{2k-1}}{2} =\frac{S}{2}$$

For $n \geq 4$ odd 

Since the LHS sum is cyclic, without loss of generality we can assume that $x_{2k+1}$ (otherwise reorder them) is the smallest term. Then $x_{2k+1} \leq x_4$ (here is where we need $n \geq 4$.)

$$x_1x_2+x_2x_3+....+x_{2k+1}x_1 \leq x_1x_2+x_2x_3+....+x_{2k}x_{2k+1}+x_{4}x_1  \leq (x_1+x_3+..+x_{2k} )( x_2+x_4+...+x_{2k-1})$$

Again BY AM_GM you get

$$\sqrt{x_1x_2+x_2x_3+....+x_{2k+1}x_1} \leq \frac{x_1+x_3+..+x_{2k+1} + x_2+x_4+...+x_{2k}}{2} = \frac{S}{2} $$
This is WRONG. It is kept here so that no one else will make the same blunder. 

The answer is $\frac{S^2}{4}$. There are $nC_2$ answers that will give this value. All of them are the all-possible permutations of the vector $x=[\frac{S}{2},\frac{S}{2},0,0,\dots,0]^T$. I was able to prove this since I already knew the solution from the comments of user N.S. on user Ross Millikan's answer. So the credit goes to him. I will demonstrate the concepts using $5 \times 5$ matrix. The result is easily generalizable. 

Define column vector $x=[x_1,x_2,x_3,x_4,x_5]^T$. Then the function in question can be written as 
\begin{align}
f(x)=x_1x_2+x_2x_3+x_3x_4+x_5x_1=x^TQx
\end{align}
where 
\begin{align}
Q=\begin{bmatrix}0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 \\0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 \\0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 \\1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\\end{bmatrix}
\end{align}
Note that $Q$ is a permutation matrix and also non-symmetric. For every non-symmetric matrix $Q$, we have $x^TQx=x^TCx$ where $C=(1/2)*(Q+Q^T)$ and is a symmetric matrix. So we have
\begin{align}
f(x)=x^TCx
\end{align}
Also note that 
\begin{align}
C=\begin{bmatrix}0 &amp; .5 &amp; 0 &amp; 0 &amp; .5 \\ .5 &amp; 0 &amp; .5 &amp; 0 &amp; 0 \\0 &amp; .5 &amp; 0 &amp; .5 &amp; 0 \\0 &amp; 0 &amp; .5 &amp; 0 &amp; .5 \\.5 &amp; 0 &amp; 0 &amp; .5 &amp; 0 \\\end{bmatrix}
\end{align}
Note that the diagonals on either side of the main diagonal are all .5 and values on top-right and left-bottom corner are also $.5$. Now $C$ is a symmetric matrix and hence
\begin{align}
\lambda_{min}(C)\leq x^TCx \leq \lambda_{max}(C)\text{ $\quad \forall x,$  $x^Tx=1$}
\end{align}
Now $C$ is a doubly stochastic matrix (column sum and row sum is one). So $1$ is always an eigenvalue. Most importantly, $C$ is an irreducible primitive matrix. This follows from perron-frobenius theory. Hence $1 $ is the largest eigenvalue. Now observe that $x=[\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}},0,0,0]^T$ has $f(x)=x^TCx=1$. Also it has unit norm. In fact, all permutations of this vector (all possible rearrangements of its entries), has the same value for $f(x)$ and they all have unit norm. This $f(x)$ is always maximized in this unit-vectors direction. Now $x^Tx=1$ is not our requirement. But, sum of its elements should be $S$. From the above the discussion, one can conclude that all the elements except two of vector $x$ should be zero and the non-zero entries should be equal if $f(x)$ is to be maximized. By symmetry, it is see to that all permutations of the vector $x=[\frac{S}{2},\frac{S}{2},0,0,0]$ is the only set of vectors that satisfies the sum condition while giving the maximum of $f(x)$.