$X$ is a set of $2020$ distinct real numbers. Prove that there exist $a,b\in \mathbb{R}$ and $A\subset X$ such that $$\sum_{x\in A}(x-a)^2 +\sum_{x\in X\backslash A}(x-b)^2\le \frac{1009}{1010}\sum_{x\in X}x^2$$
Problem
Source: 2020 Korean MO winter camp Test 1 P2
Tags: algebra
08.09.2020 17:40
As a step towards complete proof: the numbers $a,b$ minimizing the left hand side are \[ a=\frac{1}{|A|} \sum_{x\in A} x \quad\text{and}\quad b=\frac{1}{2020-|A|}\sum_{x\notin A}x. \]With this, it boils down showing there is a subset $A$ so that \[ \frac{1}{1010}\sum_{x\in X}x^2 \le \frac{1}{|A|} \left(\sum_{x\in A}x\right)^2 + \frac{1}{|A^c|} \left(\sum_{x\in A^c}x\right)^2. \]Let $X=\{x_i:1\le i \le 2020\}$. Supposing $\sum_{1\le i<j\le 2020} x_i x_j\ge 0$, I can show the existence of such a subset $A$ through probabilistic method (try it yourself: suppose $X=\{x_1,\dots,x_n\}$, and $\mathbb{P}(x_i\in A)=p$ independently, where $p$ can be taken, e.g., $1/2$). My argument stops short though, in the opposite regime; and I am fairly curious to see a complete solution.
08.09.2020 23:29
A complete solution: I will use the following identity (that was used indirectly by @grupyorum in his partial solution):
Therefore, the problem reduces to show the existence of $A \subset X$ with $$ \frac{1}{1010} \sum_{x \in X} x^2 \le (\frac{1}{A} + \frac{1}{A^c}) (\sum_{ x \in A} x)^2 := f(A)$$ By allowing $A$ with $|A|=a$ to be the set of positive elements in $X$, we get $$f(A)=(\frac{1}{A} + \frac{1}{A^c}) (\sum_{ x \in A} x)^2 \ge \frac{2020}{a(2020-a)} (\sum_{x\in A} x^2)$$ Similarly, by changing $A$ to $A^c$, the non-positive numbers, we get $$f(A^c)=(\frac{1}{A} + \frac{1}{A^c}) (\sum_{ x \in A^c} x)^2 \ge \frac{2020}{a(2020-a)} (\sum_{x\in A^c} x^2)$$ Taking their average, we see that $$\frac{f(A)+f(A^c)}{2} \ge \frac{1010}{a(2020-a)} (\sum_{x \in X} x^2) \ge \frac{1010}{1010^2} (\sum_{x \in X} x^2) $$ which solves the problem.
27.02.2021 18:26
Why do I find that1009/1010 can be changed into 504/505?