Maximize $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} $$
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..).