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>2$) with a fixed sum $S$.
What is the maximum of $x_1x_2+x_2x_3+\cdots+x_nx_1$?
 A: 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} $$
A: I have to solve this in 3 parts. First for $n=3$, then for $n=4$ and finally for $n>4$.

For $n=3$ we can take a tranformation $x'_1=x'_2=(x_1+x_2)/2$ and $x'_3=x_3$. $\sum x_i$ remains fixed while $\sum{x'_i*x'_{i+1}}-\sum{x_i*x_{i+1}} = (x_1+x_2)^2/4-x_1*x_2 = (x_1^2+2x_1x_2+x_2^2)/4-x_1*x_2 = (x_1^2-2x_1x_2+x_2^2)/4 = (x_1-x_2)^2/4$
which is $>0$ if $x_1$ differs from $x_2$.
So an optimal solution must have the first two terms equal (otherwise we can apply this transformation and obtain a higher value), but you can cycle the terms, so they must be all equal to $S/3$ for a total sum of $S^2/3$.

For $n=4$ the transformation $x'_1=x_1+x_3$, $x'_3=0$ doesn't change the result, so we take an optimal solution, sum the odd and even terms, and the problem becomes finding the maximum of $(\sum x_{odd})*(\sum x_{even})$, that is maximized if both terms are equal to $S/2$, for a total of $S^2/4$.

For $n>4$, I have to prove this lemma first:

For $n>4$, there is at least one optimal configuration that has at least
  one index $i$ such that $x_i=0$

Take a configuration that is optimal and such that every $x_i>0$ and $x_1 = max(x_i)$.
Now use the following transformation: $x'_2=x_2+x_4$, $x'_4=0$. $\sum x_i$ remains the same but $\sum{x'_i*x'_{i+1}}-\sum{x_i*x_{i+1}}=x_1*(x_2+x_4)+(x_2+x_4)*x_3+\sum_{i>4}{x_i*x_{i+1}}-\sum{x_i*x_{i+1}} = x_1*x_4-x_4*x_5 = x_4*(x_1-x_5) = x_4*(max(x_i)-x_5) \geq x_4*(x_5-x_5) = 0$
So we have another optimal solution with a $0$.
Given that at least an optimal solution contains a $0$ for every $n>4$, the maximum value of $\sum{x_i*x_{i+1}}$ must be non-increasing for $n$ (otherwise we can take a solution for $n$ with a $0$ inside, remove that $0$, and obtain a higher solution for $n-1$).
Now the value of the sum must be $\leq S^2/4$, but taking $x_1=x_2=S/2$ gives that sum, so that configuration is an optimal one, for a sum of $S^2/4$.
This proves that the maximum is $S^2/3$ if $n=3$ and $S^2/4$ otherwise.
I am not satisfied with this answer, because it breaks down to a lot of case analysis. I am still curious to see a simpler proof (or one that requires less space..).
A: This should be a comment, but I don't have the reppts.
Consider $x^n-Sx^{n-1}+e_2x^{n-2}+\ldots+(-1)^ne_n=\prod_{i=1}^n(x-x_i)$, rephrasing, quite wrongly, the question to be about finding the maximal $e_2$.
Let $x_i=\frac{S}{n}\forall i$. Then $(x-\frac{S}{n})^n=x^n-n(\frac{S}{n})x^{n-1}+{n\choose 2}(\frac{S}{n})^2x^{n-2}+\ldots$ so we can get as high as $\frac{n-1}{2n}S^2$; tending to but always smaller than $\frac{S^2}{2}$ in general.
This is $\frac{S^2}{3}$ for $n=3$, and $\frac{3}{8}S^2>\frac{S^2}{4}$ for $n=4$.
Edit: $e_2\geq x_1x_2+x_2x_3+\ldots+x_nx_1$, not necessarily equal. Keeping it up, as someone else may make the same error.
A: Consider graph $G=(V,E)$, where $V=\{1,2,\ldots,n\}$ and corresponding sum $F(x_1,x_2,\ldots,x_n)=\sum\limits_{ij\in E}{x_ix_j}$. We will prove that for $x_1,x_2,\ldots,x_n\in[0,1]$ such that $\sum\limits_{i=1}^{n}x_i=1$ the maximum of $F(x_1,x_2,\ldots,x_n)$ is equal to $\dfrac{1}{2}-\dfrac{1}{2\omega(G)}$, where $\omega(G)$ is a clique number of graph $G$. Firstly, note that the set
$$
K=\left\{(x_1,x_2,\ldots,x_n)\mid x_i\in [0,1], \sum_{i=1}^{n}x_i=1\right\}
$$
is compact and $F$ is continious, so the maximum of $F$ is attained at some point $A_0=(x_1,x_2,\ldots,x_n)\in K$. We will suppose that among all maxima of $F$ in $E$ point $A_0$ has the least possible number of nonzero coordinates. Now we will prove that the set $C$ of vertices $i\in V$ such that $x_i>0$ form a clique in the graph $G$.
Indeed, consider two indices $i$ and $j$ such that $x_i,x_j>0$. If $ij\notin E$, then consider point $A_t(x_1,\ldots,x_i+t,\ldots,x_j-t,\ldots,x_n)\in K$ (for some small $t$) and the value of $F$ at this point. Note that
$$
F(A_t)-F(A_0)
$$
is a linear function of the variable $t$ (here we use our assumption $ij\notin E$; terms with $t^2$ can appear only in $(x_i+t)(x_j-t)$) and it's well-defined on some interval $(-\varepsilon,\varepsilon)$ (we can suppose that $A_t\in K$ for $|t|<\varepsilon$).
Since $F(A_t)-F(A_0)\leq 0$ for $|t|\leq\varepsilon$, $F(A_t)$ should be constant, so for all $t$ we have $F(A_t)=F(A_0)$. Thus, for all $t$ such that $A_t\in K$ the point $A_t$ is a maximum of $F$.
Now, observe that $x_i+x_j\leq 1$, so for $t=x_j$ point $A_{x_j}\in K$ has less nonzero coordinates than $A_0$ and it contradicts our assumption.
Thus, vertices of $C=\{i\mid x_i>0\}$ form a clique in the graph $G$. In this case we can compute and estimate the value of $F$ at $A_0$; the first inequality is a consequence of $|C|\cdot\sum\limits_{i\in C}x_i^2\geq\left(\sum\limits_{i\in C}x_i\right)^2$:
$$
F(A_0)=\sum_{ij\in E}x_ix_j=\sum_{i,j\in C, ij\in E}x_ix_j\leq\frac{|C|-1}{2|C|}\cdot \left(\sum_{i\in C}x_i\right)^2=\frac{|C|-1}{2|C|}=\frac{1}{2}-\frac{1}{2|C|}\leq\frac{1}{2}-\frac{1}{2\omega(G)}.
$$
Hence, $F(x_1,\ldots,x_n)\leq\dfrac{1}{2}-\dfrac{1}{2\omega(G)}$, as desired.
Finally, note that if $\{i_1,i_2,\ldots,i_k\}$ is a clique of size $k=\omega(G)$ in the graph $G$, then $F(x_1,\ldots,x_n)=\dfrac{1}{2}-\dfrac{1}{2\omega(G)}$, where $x_{i}=\frac{1}{k}$ if $i=i_{j}$ for some $j$ and $0$ otherwise (it follows from the previous computations).
Therefore,
$$
\max_{K} F=\dfrac{1}{2}-\dfrac{1}{2\omega(G)}.
$$

Now return to the original problem. In this case $G=C_n$ (cycle on $n$ vertices), so for $n=3$ the maximum value is $\frac{1}{2}-\frac{1}{6}=\frac{1}{3}$ and for $n>2$ it equals $\frac{1}{2}-\frac{1}{4}=\frac{1}{4}$.
A: 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 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 1 \\1 & 0 & 0 & 0 & 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 & .5 & 0 & 0 & .5 \\ .5 & 0 & .5 & 0 & 0 \\0 & .5 & 0 & .5 & 0 \\0 & 0 & .5 & 0 & .5 \\.5 & 0 & 0 & .5 & 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)$. 
