Problem 1971

Answer: $K = - (n-1)/2$.

Solution 1. 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/(2t)$. 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 $(x_{1}, \ldots, x_{n})$ 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 $(x_{1}, \ldots, x_{n})$ 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
$$\begin{equation*} \sum_{i<j} z_{i} z_{j} = \sum_{q=0}^{n-1} \sum_{\substack{i+j \equiv q \ (\bmod n) \\ i \neq j \ (\bmod n)}} z_{i} z_{j} = \sum_{p=1}^{\left\lfloor \frac{n-1}{2} \right\rfloor} \sum_{\substack{i+j \equiv 2p-1, 2p \ (\bmod n) \\ i \neq j \ (\bmod n)}} z_{i} z_{j} + L, \tag{1} \end{equation*}$$
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 2p-1, 2p \ (\bmod n) \\ i \neq j \ (\bmod n)}} z_{i} z_{j} = \sum_{k=1}^{n-1} y_{k} y_{k+1},$$
because we may choose $y_{2i-1} = z_{i+p-1}$ for $1 \leqslant i \leqslant (n+1)/2$ and $y_{2i} = 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
$$\begin{equation*} x_{1} \leqslant x_{2} \leqslant \cdots \leqslant x_{k} \leqslant 0 \leqslant x_{k+1} \leqslant \cdots \leqslant x_{n}. \tag{2} \end{equation*}$$

## 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
$$\{z_{1}, z_{n-1}\}, \{z_{2}, z_{n-2}\}, \ldots, \{z_{(n-1)/2}, z_{(n+1)/2}\}$$
are some permutation of
$$\{x_{1}, x_{2}\}, \{x_{3}, x_{4}\}, \ldots, \{x_{n-2}, x_{n-1}\},$$
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} 2L = (x_{1} x_{2} + \cdots + x_{n-1} x_{n}) + (x_{1} x_{2} + \cdots + x_{n-1} x_{n}) \geqslant (x_{2} x_{3} + \cdots + x_{n-1} x_{n}) + 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_{2i-1} = z_{-i}$, $x_{2i} = z_{i}$ (again taking indices modulo $n$). We have that
$$L = \sum_{\substack{i+j \equiv 0, -1 \ (\bmod n) \\ i \neq j \ (\bmod n)}} 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 $(x_{1}, \ldots, x_{n})$. 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\} \to \{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\} \to \{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$.