Where is Day4 P3? I couldn't find it anywhere.

We claim that the desired maximum value of the sum is $\frac{n^2}{16}.$ In order to achieve this, let $a_1 = a_{\frac{n}{2} + 1} = \frac12$ and all other $a_i$'s be zero. Now, we will show that this is optimal. Let $d(i, j)$ denote the distance between $i, j$ modulo $n$, i.e., it's the minimum of $|i - j|, n-|i-j|.$ Notice that the sum in the problem can now be written simply as: $$S = \sum_{1 \leq i < j \leq n} d(i, j)^2 a_ia_j.$$Let $b_i = a_i + a_{i+1} + \cdots + a_{i + \frac{n}{2} - 1}$ for each $1 \leq i \leq n,$ where the indices are taken modulo $n$. Note that $b_i + b_{i + \frac{n}{2}} = 1 \Rightarrow b_ib_{i + \frac{n}{2}} \leq \frac14$ for $1 \leq i \leq \frac{n}{2}.$ Then, observe that: $$T = \frac{n}{2} \sum_{i = 1}^{\frac{n}{2}} b_ib_{i+\frac{n}{2}} \leq \frac{n}{2} * \frac{n}{2} * \frac{1}{4} = \frac{n^2}{16}.$$ We claim that $S \leq T.$ In order to show this, we will prove that the coefficient of $a_ia_j$ in $S$ is at most the coefficient of $a_ia_j$ in $T$, for all $i, j.$ However, this is clear, since the $a_ia_j-$coefficient in $S$ is just $d(i, j)^2,$ while that in $T$ is $\frac{n}{2} * d(i, j),$ clearly at least as large. $\square$

Pathological wrote: We claim that the desired maximum value of the sum is $\frac{n^2}{16}.$ In order to achieve this, let $a_1 = a_{\frac{n}{2} + 1} = \frac12$ and all other $a_i$'s be zero. Now, we will show that this is optimal. Let $d(i, j)$ denote the distance between $i, j$ modulo $n$, i.e., it's the minimum of $|i - j|, n-|i-j|.$ Notice that the sum in the problem can now be written simply as: $$S = \sum_{1 \leq i < j \leq n} d(i, j)^2 a_ia_j.$$Let $b_i = a_i + a_{i+1} + \cdots + a_{i + \frac{n}{2} - 1}$ for each $1 \leq i \leq n,$ where the indices are taken modulo $n$. Note that $b_i + b_{i + \frac{n}{2}} = 1 \Rightarrow b_ib_{i + \frac{n}{2}} \leq \frac14$ for $1 \leq i \leq \frac{n}{2}.$ Then, observe that: $$T = \frac{n}{2} \sum_{i = 1}^{\frac{n}{2}} b_ib_{i+\frac{n}{2}} \leq \frac{n}{2} * \frac{n}{2} * \frac{1}{4} = \frac{n^2}{16}.$$ We claim that $S \leq T.$ In order to show this, we will prove that the coefficient of $a_ia_j$ in $S$ is at most the coefficient of $a_ia_j$ in $T$, for all $i, j.$ However, this is clear, since the $a_ia_j-$coefficient in $S$ is just $d(i, j)^2,$ while that in $T$ is $\frac{n}{2} * d(i, j),$ clearly at least as large. $\square$ Thank you very much.

Nice proof by pathological. This is another proof which is a lot less elegant than @pathological's, but give solution also for odd $n$. Since the set of $(a_1 , ... ,a_n)$ in $\mathbb{R}^n$ is compact, the maximum exists. Choose the maximum with maximal number of zeroes and denote it by $(a_1 , ... ,a_n )$. Obviously, number of zeroes is at most $n-2$. For $a_i, a_j >0$, substitute them by $a_i - \epsilon ,a_j + \epsilon$. The variance is $-d(i,j)^2 \epsilon^2 + A(i,j) \epsilon$ for some $A(i,j)$ is $\sum_{k} a_k d(j,k)^2 - \sum_{k} a_k d(i,k)^2$. If $A(i,j)$ is not zero for some $i,j$ with $a_i, a_j >0$, there exists small $\epsilon$ such that the variance is positive. Therefore, $A(i,j)=0$ for all $a_i, a_j >0$. Next, assume $a_i, a_j, a_k >0$ and $d(i,j)+d(j,k)=d(i,k)$. Substitute $a_i + \epsilon , a_j - \epsilon -\delta , a_k +\delta$, the variance is $-d(i,j)^2 \epsilon ^2 -d(j,k)^2 \delta ^2 + (d(i,k)^2 -d(i,j)^2-d(j,k)^2) \epsilon \delta+A(j,i)\epsilon +A(j,k)\delta$. Since $A$ is zero and by assumption, the variance is precisely $-(d(i,j)\epsilon +d(j,k) \delta)^2$. So, if we take $d(i,j)\epsilon +d(j,k) \delta=0$, the variance is zero and we can again create new zero among $a_i, a_j, a_k$. Therefore, for any $a_i, a_j, a_k>0$, $d(i,j)+d(j,k) \ne d(i,k)$. However, there are always such $a_i, a_j, a_k$ when there are four non-zero elements. Therefore, there are at most three non-zero elements and rest is easy. Rmk) I think one can also solve the problem by attacking the first fact: $A(i,j)=0$ for all $a_i, a_j>0$, which means $\sum_k a_k d(i,k)^2$ is constant for $a_i >0$. Someone may try in this direction.

i got the answer to be as n/2 which is greater than n^2/16 at n<8 because at i=k ,j=n/2+k we have the largest term and also then i applied jensens inequality

Can denery wrote: i got the answer to be as n/2 which is greater than n^2/16 at n<8 because at i=k ,j=n/2+k we have the largest term and also then i applied jensens inequality Can you elaborate

The answer is $\frac{n^2}{16}$, with the construction being $a_1=a_{n/2+1} = \frac 12$. By compactness, the maximum exists, say it holds at $(a_1,\cdots,a_n)$. For brevity let $m=\frac n2$ and $d(k,j) = \min\{j-k, 2m+k-j\}$ for $1\le k<j\le 2m$. If $k=j$ then $d(k,k)=0$ and if $k>j$ then $d(k,j)=d(j,k)$. Then we let $T_k = \sum_j d(k,j)^2 a_j$. Then if $a_k,a_l > 0$ and $T_k \ne T_l$, then WLOG $T_k<T_l$ and we can replace $(a_k,a_l)$ with $(a_k-\epsilon, a_l+\epsilon)$ such that the sum would increase, absurd! Therefore, for all $k$ such that $a_k>0$ we have $T_k=S$ for some constant $S$ independent of $k$. Then our original expression is $$\frac 12 \sum_{k \colon a_k>0} a_kT_k = \frac S2 \sum_{k \colon a_k>0} a_k = \frac S2$$ Hence it suffices to show that $S \le \frac{m^2}{2}$. Let $d$ be the largest number such that there exists $k,j$ such that $a_ka_j > 0$ and $d(k,j) = d$. We say $f(k,j)=d(k,j)$ if $d(k,j)\le d$, and $f(k,j)=0$ otherwise. Suppose $a_ja_{j+d}>0$ (indices mod $2m$). We can clearly replace $T_j$ with $\sum f(k,j)a_k$. The key is to show that $T_j + T_{j+d} \le m^2$. Note that $$T_j+T_{j+d} = \sum_{k} (f(k,j) + f(k,j+d)) a_k$$ It suffices to prove that $f(k,j) + f(k,j+d) \le m^2$. Note $d\le m$ so we casework: if $d<m$ and $k\notin \{j,\cdots,j+d\}$ then one of $f(k,j), f(k,j+d)$ is 0 and the other is at most $d^2\le m^2$; otherwise it is $(k-j)^2 + (j+d-k)^2 \le d^2$ as well. When $d=m$ we can swap $j,j+d$ to make sure $k\in \{j,\cdots,j+d\}$.

This is not a hard problem in TST3 I think, my solution is similar to above, and DFT can also kill this. But I hope someone can explain the motivation of this strange solution: Because $\sin\frac {(j-i)\pi}n\ge\frac 2n\min\{j-i,n-j+i\}$ holds for all $1\le i<j\le n,$ we only need $$\frac {n^2}4\sum_{1\le i<j\le n}\sin^2\frac {(j-i)\pi}na_ia_j\le\frac{n^2}{16}\iff\sum_{i,j=1}^n\sin^2\frac {(j-i)\pi}na_ia_j\le\frac 12.$$$$\iff\sum_{i,j=1}^n\cos\frac{2(j-i)\pi}na_ia_j\ge 0\iff\left(\sum_{i=1}^n\cos\frac{2i\pi}na_i\right)^2+\left(\sum_{i=1}^n\sin\frac{2i\pi}na_i\right)^2\ge 0.\Box$$