International Mathematical Olympiad

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\ne 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⩾(n-3)t^2-1⩾-1.$$ This justifies that the $n$-tuple $(x_1,\dots ,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⩾-(n-1)/2$ for any Shiny choice of the $x_i$.

From now onward, assume that $(x_1,\dots ,x_n)$ is a Shiny $n$-tuple. Let the $z_i$ ($1⩽i⩽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{array}{c}\sum _{i<j}{z}_i{z}_j=\sum _{q=0}^{n-1}\sum _{\begin{array}{c}i+j\equiv q(\mathrm{mod}n)\\ i\ne j(\mathrm{mod}n)\end{array}}{z}_i{z}_j=\sum _{p=1}^{\lfloor \frac{n-1}{2}\rfloor }\sum _{\begin{array}{c}i+j\equiv 2p-1,2p(\mathrm{mod}n)\\ i\ne j(\mathrm{mod}n)\end{array}}{z}_i{z}_j+L,\end{array}\text{\hspace{1em}(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,\dots ,\lfloor (n-1)/2\rfloor$, there is some permutation $y_i$ of the $z_i$ such that $$\sum _{\begin{array}{c}i+j\equiv 2p-1,2p(\mathrm{mod}n)\\ i\ne j(\mathrm{mod}n)\end{array}}{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⩽i⩽(n+1)/2$ and $y_{2i}=z_{p-i}$ for $1⩽i⩽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⩾-\lfloor \frac{n-1}{2}\rfloor +L.$$ It remains to show that, for each $n$, there exists some permutation $z_i$ of the $x_i$ such that $L⩾0$ when $n$ is odd, and $L⩾-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{array}{c}{x}_1⩽x_2⩽\cdots ⩽x_k⩽0⩽x_{k+1}⩽\cdots ⩽x_n.\end{array}\text{\hspace{1em}(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,\dots ,x_{n-2}{x}_{n-1}⩾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}⩾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}\},\dots ,\{z_{(n-1)/2},z_{(n+1)/2}\}$$ are some permutation of $$\{x_1,x_2\},\{x_3,x_4\},\dots ,\{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\ne 1$. Now, we have $$\begin{array}{c}2L=(x_1{x}_2+\cdots +x_{n-1}{x}_n)+(x_1{x}_2+\cdots +x_{n-1}{x}_n)⩾(x_2{x}_3+\cdots +x_{n-1}{x}_n)+x_k{x}_{k+1}\\ ⩾x_2{x}_3+\cdots +x_{n-1}{x}_n+x_n{x}_1⩾-1\end{array}$$ 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⩽x_k⩽0⩽x_{k+1}⩽x_n$, and the third inequality holds because the $x_i$ are assumed to be Shiny. We thus have that $L⩾-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 _{\begin{array}{c}i+j\equiv 0,-1(\mathrm{mod}n)\\ i\ne j(\mathrm{mod}n)\end{array}}{z}_i{z}_j$$ as desired.

---

Alternative solution.

We present another proof that ${\sum }_{i<j}{x}_i{x}_j⩾-(n-1)/2$ for any Shiny $n$-tuple $(x_1,\dots ,x_n)$. Assume an ordering of the $x_i$ as in (2), and let $\ell =n-k$. Assume without loss of generality that $k⩾\ell$. Also assume $k\ne n$, (as otherwise, all of the $x_i$ are nonpositive, and so the inequality is trivial). Define the sets of indices $S=\{1,2,\dots ,k\}$ and $T=\{k+1,\dots ,n\}$. Define the following sums: $$K=\sum _{\begin{array}{c}i<j\\ i,j\in S\end{array}}{x}_i{x}_j,M=\sum _{\begin{array}{c}i\in S\\ j\in T\end{array}}{x}_i{x}_j,\text{ and }L=\sum _{\begin{array}{c}i<j\\ i,j\in T\end{array}}{x}_i{x}_j$$ By definition, $K,L⩾0$ and $M⩽0$. We aim to show that $K+L+M⩾-(n-1)/2$.

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

## Case 1: $k>\ell$.

Consider all permutations $\varphi :\{1,2,\dots ,n\}\to \{1,2,\dots ,n\}$ such that ${\varphi }^{-1}(T)=\{2,4,\dots ,2\ell \}$. Note that there are $k!\ell !$ such permutations $\varphi$. Define $$f(\varphi )=\sum _{i=1}^{n-1}{x}_{\varphi (i)}{x}_{\varphi (i+1)}$$ We know that $f(\varphi )⩾-1$ for every permutation $\varphi$ with the above property. Averaging $f(\varphi )$ over all $\varphi$ gives $$-1⩽\frac{1}{k!\ell !}\sum _{\varphi }f(\varphi )=\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 $\varphi$, and there are $k(k-1)/2$ products in $K$, of which $k-\ell -1$ are selected for each $\varphi$. We now have $$K+L+M⩾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⩽n-1$ and $K,L⩾0$, we get the desired inequality.

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

We do a similar approach, considering all $\varphi :\{1,2,\dots ,n\}\to \{1,2,\dots ,n\}$ such that ${\varphi }^{-1}(T)=\{2,4,\dots ,2\ell \}$, and defining $f$ the same way. Analogously to Case 1, we have $$-1⩽\frac{1}{k!\ell !}\sum _{\varphi }f(\varphi )=\frac{2\ell -1}{k\ell }M$$ because there are $k\ell$ products in $M$, of which $2\ell -1$ are selected for each $\varphi$. Now, we have that $$K+L+M⩾M⩾-\frac{n^2}{4(n-1)}⩾-\frac{n-1}{2},$$ where the last inequality holds because $n⩾4$.