Where do you guys find the 2017 shortlist?

The answer is $K=\frac{1-n}{2}$ , i tried small cases , i would be glad to see the solution , it's a nice problem though !

Richard-Yu wrote: Where do you guys find the 2017 shortlist? imo-official.org/problems.aspx

Thank you

Richard-Yu wrote: Where do you guys find the 2017 shortlist? https://www.imo-official.org/problems/IMO2017SL.pdf

Note that the sum condition implies we can order the $x_i$ however we want, so WLOG $x_1\le x_2\le\cdots \le x_k\le 0 \le x_{k+1}\le \cdots \le x_n$ (assuming $1\le k\le n$). Moreover, for a permutation $\pi$ of $\{1,2,\cdots, n\}$, let $S(\pi)=\sum_{i=1}^{n-1} x_{\pi(i)}x_{\pi(i+1)}$. Now WLOG $k\le n-k$, so that there are more positive terms. Also, let $S=\{1,2,\cdots, k\}$ and $T=\{k+1,\cdots, n\}$. Additionally, define $A$ as the average of all the values of form $x_ix_j$ where $i,j\in S$, $B$ as the average of all the values of form $x_ix_j$ where $i\in S, j\in T$, and $C$ as the average of the values of form $x_ix_j$ with $i,j\in T$ (and $i\neq j$). By averaging all the inequalities of form $S(\pi)\ge -1$ for all permutations $\pi$ that alternate between positive and negative terms, i.e. $\pi(2), \pi(4),\cdots, \pi(2k)\in S$, we get $(2k)B+(n-1-2k)C\ge -1$ if $2k<n$ and $(n-1)B\ge -1$ if $n=2k$. We trivially have $A,C\ge 0$ and $B\le 0$. Note that $\sum \limits_{1 \leq i < j \leq n} x_i x_j=\binom{k}{2}A+k(n-k)B+\binom{n-k}{2}C$. When $n=2k$, note that the sum is at least $$k(n-k)B=\frac{n^2}{4}B\ge \frac{-n^2}{4(n-1)}\ge \frac{1-n}{2}$$On the other hand, when $n>2k$, the sum is at least $$k(n-k)B+\binom{n-k}{2}C\ge (n-k)\left(\frac{-1-(n-1-2k)C}{2}\right)+\binom{n-k}{2}C\ge \frac{k-n}{2}\ge \frac{1-n}{2}$$Thus it remains to show equality can be achieved, which is doable by noting $k=1$ and $C=0$ above gives equality; in particular, taking $\left(\frac{-1}{2t}, t, t, \cdots, t\right)$ and $t\rightarrow 0$ gives $\sum \limits_{1 \leq i < j \leq n} x_i x_j=\frac{1-n}{2}+t^2\binom{n-1}{2}\rightarrow \frac{1-n}{2}$.

Solution by TLP.39 We claim that the answer is $\boxed{K(n) =\frac{1-n}{2}}$ for all $n\geqslant 3$. First, let $(x_1,x_2,...,x_n)=(a,a,...,a,a,-\frac{1}{2a})$,we can see that this n-tuple is shiny and the summation is equal to $\binom{n-1}{2}a^2+\frac{1-n}{2}$. Setting $a\to 0$ prove that $K\leqslant \frac{1-n}{2}$. Now it suffices to show that the inequality holds for $K= \frac{1-n}{2}$. We will split into $2$ cases. Case 1 : There are exactly $\frac{n}{2}$ positive numbers and $\frac{n}{2}$ negative numbers. WLOG let $x_1,x_3,...x_{n-1} < 0$ and $x_2,x_4,...x_n > 0$. We also extend indices by $x_i=x_{i-n}$ for all $i>n$. Adding all cyclic variants of the assertion gives $$y_1y_2 + y_2y_3 + ... + y_{n-1}y_n + y_ny_1 \geqslant -\frac{n}{n-1}.$$Plugging in $(y_1,y_2,...,y_n) = (x_1, x_{2k+2}, x_3, x_{2k+4}, ..., x_{n-1}, x_{2k+n})$ gives $$ x_1(x_{2k}+x_{2k+2}) + x_3(x_{2k+2}x_{2k+4}) + ... + x_{n-1}(x_{2k+n-2} + x_{2k+n})\geqslant -\frac{n}{n-1} $$Thus summing up from $k=0,2,4,...,n$ gives $$\sum_{1\leqslant i , j\leqslant n , 2 \mid i,2\nmid j}x_ix_j \geqslant -\frac{n^2}{4(n-1)}.$$Hence $$\sum_{1\leqslant i < j\leqslant n}x_ix_j \geqslant \sum_{1\leqslant i , j\leqslant n , 2 \mid i,2\nmid j}x_ix_j \geqslant -\frac{n^2}{4(n-1)} \geqslant \frac{1-n}{2}$$as desired. Case 2 : Number of positive and negative reals are different. In this case, we can see that at least one of $y_1y_2 , y_2y_3 , ... , y_{n-1}y_n , y_ny_1$ must be non-negative. Hence $$ y_1y_2 + y_2y_3 + ... + y_{n-1}y_n + y_ny_1 \geqslant -1. $$Summing all inequalities of the previous form gives the desired result.

We claim that $K(n)=-(n-1)/2$. When $x_1=-\frac{1}{x_2+x_3},x_2=x_3=\dots=\frac{1}{m}$ where $m$ is an arbitrarily large positive integer. We have $\sum{x_ix_j}=-\frac{n-1}{2}+\frac{\binom{n-1}{2}}{m^2}$ and $\min(\sum{y_iy_j})=(n-3) x_2^2+2 x_1 x_2\geq -1$ so the constructed tuple is $n$-Shiny. Let $x_1\geq x_2\ge \dots \geq x_k$ be positive and $x_{k+1}\leq x_{k+2} \leq \dots \leq x_n$ be non-positive. WLOG, let $k\leq n/2$ . Else we can always consider $\{-x_1,-x_2, \dots,-x_n \}$. We first consider all permutations $\{y_1,y_2,\dots ,y_n\}$ of $\{x_1,x_2,\dots ,x_n\}$ with only $y_2,y_4,…,y_{2k}$ being positive. We sum up all the $(\sum{y_iy_j})$ in these permutations. Define a pair $x_i x_j$ to be positive-positive is both $x_i, x_j$ are positive, similarly for negative-negative and positive-negative pair. We notice by symmetry that in the sum of all the $\sum{y_i y_{i+1}}$ we considered, each positive-positive pair appears an equal number of times, same for negative-negative and negative-positive pair. Let $\alpha ,\beta ,\gamma$ represent the average values of the negative-positive, negative-negative and positive-positive pair respectively. When $2k < n$, we have $\sum{y_i y_{i+1}}\geq -1\implies 2k\alpha +(n-1-2k)\beta \geq -1$ Since in every ordered $n$-tuple we consider, $2k$ pairs are negative-positive and $n-1-2k$ are negative-negative,We have $\frac{k(n-k)}{2k}\leq \frac{n-1}{2}$ $\frac{\binom{n-k}{2}}{\binom{n}{2}}=\frac{(n-k)(n-k-1)}{n(n-1)} \geq \frac{(n-k-1)^2}{(n-1)^2} \geq \frac{n-2k-1}{n-1} \implies \frac{\binom{n-k}{2}}{n-1-2k} \geq \frac{n}{2} \geq \frac{n-1}{2}$ Hence, we have $\sum{x_i x_j}=k(n-k)\alpha+ \binom{n-k}{2} \beta+\binom{k}{2} \gamma \geq \frac{n-1}{2} (2k\alpha +(n-1-2k)\beta)\geq -\frac{n-1}{2}$ since \alpha \leq 0,\beta \geq 0,\gamma \geq 0. Therefore conclusion follows. When $n=2k$, we have $\sum{y_i y_{i+1 }}\geq -1\implies (n-1)\alpha=(2k-1)\alpha \geq -1$ We have $\frac{k(n-k)}{2k-1}=\frac{(n/2)^2}{n-1}\leq \frac{n-1}{2}$ As $n\geq 3$ and 2 divides $n$. Hence, $\sum{x_i x_j}=k(n-k)\alpha+ \binom{n-k}{2} \beta+\binom{k}{2} \gamma \geq -\frac{n-1}{2}$ And we’re done.

Judging by the complexity of the above solutions, I' ve most likely made numerous errors in this solution, yet I am still unable to detect them. Could someone please point them out for me? We will prove that $K = - \frac{n-1}{2}$. First of all, to show that this value is attainable, consider $x_i = 1$ for $i = 1, 2, \dots n-1$ and $x_n = - \frac{n-1}{2}$. Now, consider a permutation $y_i$, for which $y_j = x_n$. Then, the corresponding cyclic sum is: $y_1 y_2 + y_2 y_3 + \dots + y_{j-1} y_j + y_j y _ {j+1} + \dots + y_n y_1 = (n-2) - 2 \frac{n-1}{2} = -1$, which means the aforementioned $n$-tuple is shiny. Thus, $\sum \limits_{1 \leq i < j \leq n} x_i x_j = \sum \limits_{1 \leq i < j \leq n-1} x_i x_j + x_n(x_1 + x_2 + \dots + x_{n-1}) = \binom{n-1}{2}*1 - \frac{n-1}{2}*(n-1) = - \frac{n-1}{2}$. Now, we have to prove that $\sum \limits_{1 \leq i < j \leq n} x_i x_j \geq - \frac{n-1}{2}$. To do this, consider all inequalities $\sum \limits_{i=1}^{n-1} y_i y_{i+1} \geq -1$, for all permutations of the original $n$-tuple, and add them up. On the $RHS$ there will be a $-1$ for every permutation of the $n$-tuple, so $RHS = -n!$. Meanwhile, in the $LHS$ each summand $x_i x_j$ will appear as many times as the permutations of the $n$-tuple for which $x_i$ is next to $x_j$ (or one of them is at the beginning and the other at the end). The total number of such permutations is $2n(n-2)!$ (we can arbitrarily place $x_i$, then pick one of the $2$ neighbouring positions for $x_j$ and finally randomly place the other $n-2$ numbers). Consequently: $\sum \limits_{1 \leq i < j \leq n} 2n(n-2)!x_i x_j = 2n(n-2)! \sum \limits_{1 \leq i < j \leq n} x_i x_j \geq -n! \Leftrightarrow \sum \limits_{1 \leq i < j \leq n} x_i x_j \geq - \frac{n-1}{2}$, and we are done.

spiros_gal wrote: Then, the corresponding cyclic sum is: $y_1 y_2 + y_2 y_3 + \dots + y_{j-1} y_j + y_j y _ {j+1} + \dots + y_n y_1 = (n-2) - 2 \frac{n-1}{2} = -1$, which means the aforementioned $n$-tuple is shiny. No! Note that the sum is only until $y_{n-1}y_n$ i.e. it is not a complete cyclic sum (I made the same mistake when solving the problem for the first time).

Solved with goodbear, Th3Numb3rThr33. The answer is \(\frac{1-n}2\), achieved by taking \((\varepsilon,\varepsilon,\ldots,\varepsilon,s/\varepsilon)\) for \(s=-\frac12\) and \(\varepsilon\to0^+\). There are two main cases to consider: \bigskip First case: Say the number of nonnegative elements and the number of negative elements of \((x_1,\ldots,x_n)\) are not equal. Then for each permutation \((y_1,\ldots,y_n)\), there is an index \(i\) with \(y_iy_{i-1}\ge0\), so \(y_1y_2+\cdots+y_ny_1\ge-1\). Sum this bound over all permutations to obtain \[\sum_{i<j}x_ix_j\ge-\frac{\binom n2}n=\frac{1-n}2.\] \bigskip Second case: Say the number of nonnegative elements and the number of negative elements of \((x_1,\ldots,x_n)\) are equal; in particular, \(n\) is even. Without loss of generality \(x_i<0\) for \(i\le n\) and \(x_i\ge0\) for \(i\ge n\). By summing \(y_1y_2+\cdots+y_{n-1}y_n\ge-1\) over permutations where \(y_{2i-1}<0\) and \(y_{2i}\ge0\) for each \(i\), we have \[\sum_{i\le n}\sum_{j>n}x_ix_j\ge\frac{n^2}{4(1-n)}.\]This already finishes, since \[\sum_{i<j}x_ix_j\ge\sum_{i\le n}\sum_{j>n}x_ix_j\ge\frac{n^2}{4(1-n)}>\frac{1-n}2\]for all \(n\ge4\).

Answer: $K(n)=\frac{n-1}{2}$. Construction: This is achieved by taking $\left(\frac{(n-3)b^2+1}{2b}, -b, -b,\ldots,-b\right)$ which is shiny because $$\sum_{i=1}^{n-1} y_iy_{i+1} \geq 2\left(-b\left(\frac{(n-3)b^2+1}{2b}\right)\right)+(n-3)b^2=-(n-3)b^2-1+(n-3)b^2=-1$$and by taking $b\rightarrow 0^+$ we have $$\sum_{1\leq i<j\leq n} x_ix_j=(n-1)\frac{(n-3)b^2+1}{2b}b+{n-1\choose 2}b^2=-\frac{n-1}{2}((n-3)b^2+1)+{n-1\choose 2}b\rightarrow \frac{1-n}{2}$$Thus, $K(n)\leq \frac{1-n}{2}$. Bound: For $n=3$, assume WLOG $x_1x_2\geq 0$. Then $x_1x_2+x_2x_3+x_3x_1\geq x_2x_3+x_3x_1\geq -1$ so $K(3)\geq -1$. If some $x_i=0$, assume WLOG it is $x_n$. Then $(x_1,\ldots, x_{n-1})$ is Shiny and $\sum_{1\leq i<j\leq n} x_ix_j = \sum_{1\leq i<j\leq n-1} x_ix_j$ so inductively, $\sum_{1\leq i<j\leq n} x_ix_j\geq K(n-1)=-\frac{n-2}{2}\geq -\frac{n-1}{2}$ as needed. Now assume $x_i\neq 0$ for all $1\leq i\leq n$. First, if $n$ is odd, or if $n$ is even and NOT exactly half the $x_i$'s are positive, then in every permutation $y_1, y_2, \ldots, y_n$, if we take $y_{n+1}=y_1$ then by Pigeonhole Principle, there is $1\leq t\leq n$ such that $y_ty_{t+1}\geq 0$. Thus, $$\sum_{i=1}^n y_iy_{i+1}\geq y_{t+1}y_{t+2}+y_{t+2}y_{t+3}+\cdots+y_{t-1}y_t \geq -1$$Therefore, if $\mathcal S$ is the set of permutations of $(x_1,\ldots, x_n)$, then summing over all permutations $(y_1,\ldots, y_n)$ we have: $$\sum_{1\leq i<j\leq n} x_ix_j \geq \frac{{n\choose 2}}{n\cdot n!}\sum_{(y_1,y_2,\ldots, y_n)\in\mathcal S}\sum_{i=1}^n y_iy_{i+1}\geq \frac{1-n}{2}$$as needed. In the case that $n$ is even AND exactly $\frac{n}{2}$ of the $x_i$ are positive, assume WLOG that $x_1,x_3,\ldots, x_{n-1}>0$ and $x_2,x_4,\ldots, x_{2n}<0$. For permutation $(y_1, y_2,\ldots, y_n)$, we first take the $n$ cycles: $$\sum_{1\leq i\leq n} y_iy_{i+1}=\frac{1}{n-1}\sum_{1\leq j\leq n}\sum_{1\leq i\leq n, i\neq j} y_iy_{i+1}\geq -\frac{n}{n-1}$$We sum over all permutations $(y_1,y_2,\ldots, y_n)$ such that $y_iy_{i+1}<0$ for $i=1,2,\ldots, n$. here are exactly $\left(\left(\frac{n}{2}\right)!\right)^2$ of these (in some subset $\mathcal T\subseteq\mathcal S$, so: $$\sum_{1\leq i<j\leq n} x_ix_j\geq \sum_{r\text{ odd, } s\text{ even}} x_sx_r \geq \frac{\left(\frac n2\right)^2}{n\cdot \left(\left(\frac{n}{2}\right)!\right)^2}\sum_{(y_1,\ldots, y_n)\in\mathcal T}\sum_{i=1}^n y_iy_{i+1}\geq \frac{\left(\frac n2\right)^2}{n}\cdot \left(-\frac{n}{n-1}\right)=-\frac{n^2}{4(n-1)}\geq -\frac{n-1}{2}$$because $2(n-1)^2\geq n^2$ for all $n\geq 4$, as needed. Thus, $K(n)\geq -\frac{n-1}{2}$ always.

The answer is $K(n)=\tfrac{1-n}{2}$. Construct a graph $G=K_n$ on the $x_i$. Label each edge $x_i \sim x_j$ with a weight $x_ix_j$. The nonconstructive part of the problem is to show that if sum of the weights in any Hamiltonian path is at least $-1$, then the sum of all weights is at least $\tfrac{1-n}{2}$. Construction: Consider $(x_i)=(\varepsilon, \varepsilon, \dots, \varepsilon, -\tfrac{1}{2\varepsilon})$ for $\varepsilon \rightarrow 0$. Now set $K(n)=-\tfrac{1-n}{2}$ and do casework on the parity of $n$ Case 1, $\color{blue}n$ is odd: Partition the edges of $G$ into $\tfrac{n-1}{2}$ edge-disjoint Hamiltonian paths and $n-1$ leftover disjoint edges. The idea is to take an appropriate permutation of the vertices of any such configuration so that each leftover edge has nonnegative weight, which is easy because we can simply pair the positive terms together and the negative terms together. Since the sum of the weights of each path is at least $-1$, and thus the sum of all weights is at least $\tfrac{1-n}{2}$. Case 2, $\color{blue}n$ is even: Partition the edges of $G$ into $\tfrac{n}{2}$ edge-disjoint Hamiltonian paths. The issue is that yields only a lower bound of $-\tfrac{n}{2}$, so if we show that one of the paths has weight at least $-\tfrac{1}{2}$, then we're done. Write $\{x_i\}$ in increasing order as \[ (y_i)_{i \in [-a, b]} \]so that $y_{-a}, \dots, y_{-1}$ are all negative and $y_0, \dots, y_b$ are all nonnegative. In fact, we claim that the path \[ y_{-a} \rightarrow y_{-a+1} \rightarrow \dots \rightarrow y_{b-1} \rightarrow y_b \]has weight $w$ at least $-\tfrac{1}{2}$. In order to do this, we write $2w$ as the weight of some Hamiltonian path, and use an appropriate permutation of the $x_i$ to make this path one of the paths in the partition. Since $y_{-1}y_0 \le y_{-a}y_b$, we rearrange the edge weights and find that \[ y_b \rightarrow y_{-a} \rightarrow y_{-a+1} \rightarrow \dots \rightarrow y_{b-1} \]has weight at most $2w$. Thus we are done. Remark: Although this solution is written with a graph theoretic flavor text, it is no different from the other solutions given. We essentially formalize the combinatorial ideas involved in the problem, i.e.\ the partition into Hamiltonian paths.

We claim that the answer is $K=\tfrac{1-n}{2}$. First, we prove that $K$ works. Suppose that there are either more negative terms or more nonnegative terms in $(x_1,\ldots,x_n)$. Then by pigeonhole principle, no matter how we permute, we can always cyclically shift the permutation so that $y_ny_1\ge 0$. This implies \[\sum_{i=1}^{n}y_iy_{i+1} \ge -1.\]And if we average this over all permutations, we get the term $x_ix_j$ $2n(n-2)!$ times out of $n!$ so \[\frac{2}{n-1}\sum x_ix_j \ge -1\]which is what's desired. Suppose that there are equally many negative terms as nonnegative ones, then let's say we only consider the permutations that alternate between negative and nonnegative, starting with nonnegative. Clearly, each term $x_ix_j$ where $x_i$ is negative and $x_j$ is nonnegative appears in $\tfrac{n-1}{n^2}$ of the permutations, so \[\frac{2}{n-1}\sum x_ix_j \ge \frac{n-1}{n^2}\sum x_ix_j \ge -1\]as desired. The construction is $(x,x,\dots,x,-\tfrac{1}{2x})$ for small $x$.

Take the interpretation on $K_n$. Claim: $K(n) = \frac{-(n-1)}{2}$ is maximal. Proof. Take $x_1 = x_2 = \dots = x_{n-1} = \varepsilon, x_n = -\frac{1}{2\varepsilon}$. Then we get that \[ \sum_{1 \le i < j \le n} x_ix_j = \varepsilon^2 \cdot \frac{(n-1)(n-2)}{2} - \frac{n-1}{2} \]which approaches $-\frac{n-1}{2}$ as $\varepsilon$ approaches $0$. $\blacksquare$ Claim: $K(n) = \frac{-(n-1)}{2}$ works for odd $n$. Proof. Decompose $K_n$ into $\frac{n-1}{2}$ hamiltonian cycles. Then take the missing vertex in each cycle to be a positive edge. $\blacksquare$ Claim: If $n$ is even, this holds. Proof. Decompose $K_n$ into $\frac{n}{2}$ hamiltonian paths. It remains to show some path is at least $-\frac{1}{2}$. WLOG let $x_1 \le x_2 \le x_i \le 0 \le x_{i+1} \le \dots \le x_n$. Then note that $x_ix_{i+1}$ is the only negative term, and that $x_{i-1}x_i + x_{i+1}x_{i+2} \ge |x_ix_{i+1}|$. $\blacksquare$