Problem (Algebra):
An integer $n \geqslant 3$ is given. We call an $n$-tuple of real numbers $\left(x_{1}, x_{2}, \ldots, x_{n}\right)$ Shiny if for each permutation $y_{1}, y_{2}, \ldots, y_{n}$ of these numbers we have

$$
\sum_{i=1}^{n-1} y_{i} y_{i+1}=y_{1} y_{2}+y_{2} y_{3}+y_{3} y_{4}+\cdots+y_{n-1} y_{n} \geqslant-1
$$

Find the largest constant $K=K(n)$ such that

$$
\sum_{1 \leqslant i<j \leqslant n} x_{i} x_{j} \geqslant K
$$

holds for every Shiny $n$-tuple $\left(x_{1}, x_{2}, \ldots, x_{n}\right)$.

Solution:
First of all, we show that we may not take a larger constant $K$. Let $t$ be a positive number, and take $x_{2}=x_{3}=\cdots=t$ and $x_{1}=-1 /(2 t)$. Then, every product $x_{i} x_{j}(i \neq j)$ is equal to either $t^{2}$ or $-1 / 2$. Hence, for every permutation $y_{i}$ of the $x_{i}$, we have

$$
y_{1} y_{2}+\cdots+y_{n-1} y_{n} \geqslant(n-3) t^{2}-1 \geqslant-1
$$

This justifies that the $n$-tuple $\left(x_{1}, \ldots, x_{n}\right)$ is Shiny. Now, we have

$$
\sum_{i<j} x_{i} x_{j}=-\frac{n-1}{2}+\frac{(n-1)(n-2)}{2} t^{2}
$$

Thus, as $t$ approaches 0 from above, $\sum_{i<j} x_{i} x_{j}$ gets arbitrarily close to $-(n-1) / 2$. This shows that we may not take $K$ any larger than $-(n-1) / 2$. It remains to show that $\sum_{i<j} x_{i} x_{j} \geqslant$ $-(n-1) / 2$ for any Shiny choice of the $x_{i}$.

From now onward, assume that $\left(x_{1}, \ldots, x_{n}\right)$ is a Shiny $n$-tuple. Let the $z_{i}(1 \leqslant i \leqslant n)$ be some permutation of the $x_{i}$ to be chosen later. The indices for $z_{i}$ will always be taken modulo $n$. We will first split up the sum $\sum_{i<j} x_{i} x_{j}=\sum_{i<j} z_{i} z_{j}$ into $\lfloor(n-1) / 2\rfloor$ expressions, each of the form $y_{1} y_{2}+\cdots+y_{n-1} y_{n}$ for some permutation $y_{i}$ of the $z_{i}$, and some leftover terms. More specifically, write

$$
\sum_{i<j} z_{i} z_{j}=\sum_{q=0}^{n-1} \sum_{\substack{i+j \equiv q \\ i \neq j}} z_{i} z_{j}=\sum_{\substack{(\bmod n)}}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \sum_{\substack{i+j \equiv 2 p-1,2 p(\bmod n) \\ i \neq j}} z_{i} z_{j}+L
\tag{1}
$$

where $L=z_{1} z_{-1}+z_{2} z_{-2}+\cdots+z_{(n-1) / 2} z_{-(n-1) / 2}$ if $n$ is odd, and $L=z_{1} z_{-1}+z_{1} z_{-2}+z_{2} z_{-2}+$ $\cdots+z_{(n-2) / 2} z_{-n / 2}$ if $n$ is even. We note that for each $p=1,2, \ldots,\lfloor(n-1) / 2\rfloor$, there is some permutation $y_{i}$ of the $z_{i}$ such that

$$
\sum_{\substack{i+j \equiv 2 p-1,2 p(\bmod n) \\ i \neq j}} z_{i} z_{j}=\sum_{k=1}^{n-1} y_{k} y_{k+1}
$$

because we may choose $y_{2 i-1}=z_{i+p-1}$ for $1 \leqslant i \leqslant(n+1) / 2$ and $y_{2 i}=z_{p-i}$ for $1 \leqslant i \leqslant n / 2$.

We show (1) graphically for $n=6,7$ in the diagrams below. The edges of the graphs each represent a product $z_{i} z_{j}$, and the dashed and dotted series of lines represents the sum of the edges, which is of the form $y_{1} y_{2}+\cdots+y_{n-1} y_{n}$ for some permutation $y_{i}$ of the $z_{i}$ precisely when the series of lines is a Hamiltonian path. The filled edges represent the summands of $L$.





Now, because the $z_{i}$ are Shiny, we have that (1) yields the following bound:

$$
\sum_{i<j} z_{i} z_{j} \geqslant-\left\lfloor\frac{n-1}{2}\right\rfloor+L
$$

It remains to show that, for each $n$, there exists some permutation $z_{i}$ of the $x_{i}$ such that $L \geqslant 0$ when $n$ is odd, and $L \geqslant-1 / 2$ when $n$ is even. We now split into cases based on the parity of $n$ and provide constructions of the permutations $z_{i}$.

Since we have not made any assumptions yet about the $x_{i}$, we may now assume without loss of generality that

$$
x_{1} \leqslant x_{2} \leqslant \cdots \leqslant x_{k} \leqslant 0 \leqslant x_{k+1} \leqslant \cdots \leqslant x_{n}
\tag{2}
$$

Case 1: $n$ is odd.

Without loss of generality, assume that $k$ (from (2)) is even, because we may negate all the $x_{i}$ if $k$ is odd. We then have $x_{1} x_{2}, x_{3} x_{4}, \ldots, x_{n-2} x_{n-1} \geqslant 0$ because the factors are of the same sign. Let $L=x_{1} x_{2}+x_{3} x_{4}+\cdots+x_{n-2} x_{n-1} \geqslant 0$. We choose our $z_{i}$ so that this definition of $L$ agrees with the sum of the leftover terms in (1). Relabel the $x_{i}$ as $z_{i}$ such that

$$
\left\{z_{1}, z_{n-1}\right\},\left\{z_{2}, z_{n-2}\right\}, \ldots,\left\{z_{(n-1) / 2}, z_{(n+1) / 2}\right\}
$$

are some permutation of

$$
\left\{x_{1}, x_{2}\right\},\left\{x_{3}, x_{4}\right\}, \ldots,\left\{x_{n-2}, x_{n-1}\right\}
$$

and $z_{n}=x_{n}$. Then, we have $L=z_{1} z_{n-1}+\cdots+z_{(n-1) / 2} z_{(n+1) / 2}$, as desired.

Case 2: $n$ is even.

Let $L=x_{1} x_{2}+x_{2} x_{3}+\cdots+x_{n-1} x_{n}$. Assume without loss of generality $k \neq 1$. Now, we have

$$
\begin{gathered}
2 L=\left(x_{1} x_{2}+\cdots+x_{n-1} x_{n}\right)+\left(x_{1} x_{2}+\cdots+x_{n-1} x_{n}\right) \geqslant\left(x_{2} x_{3}+\cdots+x_{n-1} x_{n}\right)+x_{k} x_{k+1} \\
\geqslant x_{2} x_{3}+\cdots+x_{n-1} x_{n}+x_{n} x_{1} \geqslant-1
\end{gathered}
$$

where the first inequality holds because the only negative term in $L$ is $x_{k} x_{k+1}$, the second inequality holds because $x_{1} \leqslant x_{k} \leqslant 0 \leqslant x_{k+1} \leqslant x_{n}$, and the third inequality holds because the $x_{i}$ are assumed to be Shiny. We thus have that $L \geqslant-1 / 2$. We now choose a suitable $z_{i}$ such that the definition of $L$ matches the leftover terms in (1).



Relabel the $x_{i}$ with $z_{i}$ in the following manner: $x_{2 i-1}=z_{-i}, x_{2 i}=z_{i}$ (again taking indices modulo $n$ ). We have that

$$
L=\sum_{\substack{i+j \equiv 0,-1(\bmod n) \\ i \neq j j}} z_{i} z_{j}
$$

as desired.

We present another proof that $\sum_{i<j} x_{i} x_{j} \geqslant-(n-1) / 2$ for any Shiny $n$-tuple $\left(x_{1}, \ldots, x_{n}\right)$. Assume an ordering of the $x_{i}$ as in (2), and let $\ell=n-k$. Assume without loss of generality that $k \geqslant \ell$. Also assume $k \neq n$, (as otherwise, all of the $x_{i}$ are nonpositive, and so the inequality is trivial). Define the sets of indices $S=\{1,2, \ldots, k\}$ and $T=\{k+1, \ldots, n\}$. Define the following sums:

$$
K=\sum_{\substack{i<j \\ i, j \in S}} x_{i} x_{j}, \quad M=\sum_{\substack{i \in S \\ j \in T}} x_{i} x_{j}, \quad \text { and } \quad L=\sum_{\substack{i<j \\ i, j \in T}} x_{i} x_{j}
$$

By definition, $K, L \geqslant 0$ and $M \leqslant 0$. We aim to show that $K+L+M \geqslant-(n-1) / 2$.

We split into cases based on whether $k=\ell$ or $k>\ell$.

Case 1: $k>\ell$.

Consider all permutations $\phi:\{1,2, \ldots, n\} \rightarrow\{1,2, \ldots, n\}$ such that $\phi^{-1}(T)=\{2,4, \ldots, 2 \ell\}$. Note that there are $k ! \ell$ ! such permutations $\phi$. Define

$$
f(\phi)=\sum_{i=1}^{n-1} x_{\phi(i)} x_{\phi(i+1)}
$$

We know that $f(\phi) \geqslant-1$ for every permutation $\phi$ with the above property. Averaging $f(\phi)$ over all $\phi$ gives

$$
-1 \leqslant \frac{1}{k ! \ell !} \sum_{\phi} f(\phi)=\frac{2 \ell}{k \ell} M+\frac{2(k-\ell-1)}{k(k-1)} K
$$

where the equality holds because there are $k \ell$ products in $M$, of which $2 \ell$ are selected for each $\phi$, and there are $k(k-1) / 2$ products in $K$, of which $k-\ell-1$ are selected for each $\phi$. We now have

$$
K+L+M \geqslant K+L+\left(-\frac{k}{2}-\frac{k-\ell-1}{k-1} K\right)=-\frac{k}{2}+\frac{\ell}{k-1} K+L .
$$

Since $k \leqslant n-1$ and $K, L \geqslant 0$, we get the desired inequality.

Case 2: $k=\ell=n / 2$.

We do a similar approach, considering all $\phi:\{1,2, \ldots, n\} \rightarrow\{1,2, \ldots, n\}$ such that $\phi^{-1}(T)=$ $\{2,4, \ldots, 2 \ell\}$, and defining $f$ the same way. Analogously to Case 1 , we have

$$
-1 \leqslant \frac{1}{k ! \ell !} \sum_{\phi} f(\phi)=\frac{2 \ell-1}{k \ell} M
$$

because there are $k \ell$ products in $M$, of which $2 \ell-1$ are selected for each $\phi$. Now, we have that

$$
K+L+M \geqslant M \geqslant-\frac{n^{2}}{4(n-1)} \geqslant-\frac{n-1}{2}
$$

where the last inequality holds because $n \geqslant 4$.

Final answer: $-(n-1) / 2$