Find the maximum of the quadratic $\sum\limits_{1\le i$n$ be a given even number and $a_{1},a_{2},\ldots,a_{n}$ be non-negative real numbers such that
$$
a_{1} + a_{2} + \cdots + a_{n} = 1.
$$

*Find the maximum possible value of
$$
\sum_{1\ \leq\ i\ <\ j\ \leq\ n}
\min\left\{\left(i - j\right)^{2},
\left(n + i - j\right)^{2}\right\}a_{i}a_{j}.
$$

*This problem may be a quadratic problem of linear algebra. In fact, this problem comes from a high school mathematics competition, so there may be a very simple method.

 A: The maximum is $n^2/16$.
Let me rewrite the function somewhat. Consider the $n$ by $n$ matrix $M$ with entries
$M_{ij}=\min((i-j)^2, (n-|i-j|)^2)$ and let $a$ the vector with components $a_1,\dots,a_n$.
Then the function of the question is $f(a)=\frac12 a^TMa$ because the sum extends only to $i<j$.
We want to maximize $f(a)$ under the conditions that all $a_i$ are non-negative and 
$a_1+\cdots a_n=1$. We rewrite this as $a\geq0$ and $e^T\,a=1$ where $e=(1,\dots,1)^T$. 
The problem is not so simple, because the matrix $M$ is not positive definite (the diagonal is zero!).
Observe that the rows of $M$ are cyclic permutations of each other and that $M$ is symmetric. This comes from the fact
that $M_{ij}$ only depends upon $|i-j|$.
Now consider the vector $a_0=(1/2,0,\dots,0,1/2,0,\dots,0)^T$ with $1/2$ at positions $1$ and $\frac n2+1$. Then
$f(a_0)=n^2/16$. 
Since the set of all vectors $a$ satisfying the conditions $a\geq0$, $e^T\,a=1$ is compact, $f$ has a maximum on this set.
We denote by $z$ some vector where the maximum is attained. We want to show that $z$ equals $a_0$ except for
a cyclic permutation and hence the maximum is $n^2/16$. 
Claim 1: There exists $\lambda$ such that $Mz\leq2\lambda e$ and $(Mz)_i=2\lambda$ whenever $i\in S(z)$. Here $S(z)$
is the support of $z$, that is the set of indices $i$ such that $z_i\neq0$ and $(a)_i$ denotes the $i$-th component of a
vector $a$.
Observe that then $f(z)=\lambda$ since $z^Te=1.$ The above conditions are the Kuhn-Tucker conditions for our
optimisation problem, but they are easily derived here. 
Proof: $\newcommand{\eps}{\varepsilon}$
Suppose first that $f(z)=\lambda$ and $(Mz)_i\neq2\lambda$ for some $i\in S(z)$.
Then consider the vector $z+\eps e_i$, where $|\eps|$ is small and $e_i$ the $i$-th unit vector.
We calculate $(z+\eps e_i)^T M (z+\eps e_i)=z^T M z +2\eps e_i ^T Mz +\eps^2e_i^TMe_i=
2\lambda+2\eps(Mz)_i$. Put $\tilde z=(1+\eps)^{-1}(z+\eps e_i)$. Then $e^T \tilde z=1$, $\tilde z\geq0$
and $\frac12\tilde z^TM\tilde z=(\lambda+\eps(Mz)_i)/(1+\eps)^2=\lambda+\eps((Mz)_i-2\lambda)+O(\eps^2)$,
where $O(\eps^2)$ denotes terms that are smaller than $K|\eps|^2$ with some constant $K$.
If $(Mz)_i>2\lambda$, we find that $f(\tilde z)>f(z)$ for small positive $\eps$ contrary to the assumption.
If $(Mz)_i<2\lambda$, we conclude using a small negative $\eps$.
If $(Mz)_i>2\lambda$ for some $i$ for which $z_i=0$, then we obtain in the same way a contradiction
for small positive $\eps$.
Claim 2: The support $S(z)$ is symmetric in the sence that $i\in S(z)$ if and only if $i+\frac n2\in S(z)$ for $i=1,\dots,\frac n2$.
Proof: This is the most tricky part! Suppose that the support is not symmetric. Using a cyclic permutation, we can assume
that $z_{n/2}=0$, but $z_n>0$. Then we split $S(z)\setminus\{n\}$ into two parts: $S_+=\{i\in S(z)|i<n/2\}$ and 
$S_-=\{i\in S(z)|i>n/2,i\neq n\}$. Then by Claim $1$ $$(Mz)_n=\sum_{i\in S_+} i^2 z_i + \sum_{i\in S_-} (n-i)^2 z_i=2\lambda.$$
We calculate 
$$(Mz)_{n-1}=\sum_{i\in S_+} (i+1)^2 z_i+\sum_{i\in S_-} (n-i-1)^2 z_i+z_n.$$
Here we use that $n/2$ is not in $S_+$.
Therefore $(Mz)_{n-1}-(Mz)_n=2\sum_{i\in S_+} i z_i - 2\sum_{i\in S_-} (n-i) z_i+1.$
So if $\sum_{i\in S_+} i z_i \geq\sum_{i\in S_-} (n-i) z_i$ then $(Mz)_{n-1}>2\lambda$ contradicting Claim 1.
Similarly (using that $n/2$ is not in $S_-$)
$$(Mz)_{1}=\sum_{i\in S_+} (i-1)^2 z_i+\sum_{i\in S_-} (n-i+1)^2 z_i+z_n$$
and $(Mz)_{1}-(Mz)_n=-2\sum_{i\in S_+} i z_i + 2\sum_{i\in S_-} (n-i) z_i+1.$
Therefore  $(Mz)_{1}>2\lambda$ contradicting Claim 1 if $\sum_{i\in S_+} i z_i \leq\sum_{i\in S_-} (n-i) z_i$.
Altogether the assumption $z_n>0$, $z_{n/2}=0$ leads to a contradiction.
In the sequel we actually only need that $S(z)$ contains $i$ and $i+n/2$ for some $i$.
Claim 3: $z$ equals $a_0$ except for some cyclic permutation and hence $f(z)=n^2/16$.
Proof: By Claim 2 and a cyclic permutation, we can assume that 1 and $\frac n2+1$ are in $S(z)$.
Hence $S(a_0)\subseteq S(z)$.
Observe that $a_0$ satisfies the conditions of Claim 1 with $\mu=\frac{n^2}{16}$ instead of $\lambda$, because
$(\frac n2)^2> (\frac n2-i)^2+i^2$ for $i=1,\dots,\frac n2-1$.
We calculate $a_0^TMa_0-z^TMz=(a_0-z)^TMz+a_0^TM(a_0-z)=(a_0-z)^TMz+(a_0-z)^TMa_0$ because $M$ is symmetric.
Now $Mz=2\lambda e - u$ where $u\geq0$ and $S(u)\cap S(z)=\emptyset$. Hence 
$(a_0-z)^TMz=2\lambda(a_0-z)^Te- (a_0-z)^Tu=0$ because $a_0^Te=1=z^Te$ and $S(a_0-z)\subseteq S(z)$.
We also have $Ma_0=2\mu e-v$, where $\mu=\frac {n^2}{16}$ and $v\geq0$, $S(v)\cap S(a_0)=\emptyset$.
Above, we have seen that even $S(v)=\{1,\dots,n\}\setminus\{1,\frac n2+1\}$.
Hence $(a_0-z)^TMa_0=2\mu(a_0-z)^Te-(a_0-z)^Tv=z^Tv$.
Altogether we have $a_0^TMa_0-z^TMz=z^Tv\geq0$. Since the maximum is attained in $z$ by assumption, we have $z^Tv=0$, therefore $S(z)=S(a_0)$. Hence
$z=a_0$ by Claim 1 because both satisfy the same $2$ by $2$ linear system with non-singular coefficient matrix. This completes the proof.
