The sum of $2025$ non-negative real numbers is $1$. Prove that they can be organized in a circle in such a way that the sum of all the $2025$ products of pairs of neighbouring numbers isn't greater than $\frac{1}{2025}$.
Problem
Source: Brazil Cono Sur TST 2024 - T2/P1
Tags: inequalities, quadratic mean
12.11.2024 01:31
We'll solve the problem for any positive integer $n$. (There is a typo, it's actually lower or equal.) Let $\{a_1, a_2, \dots\ a_n\}$ be the numbers. FTSOC assume that for any arrangement of the numbers the sum of the products is more than $\frac{1}{n}$. Then, summing all the possibilities we get: $\frac{(n-1)!\cdot n}{\binom n 2}\sum _{i\neq j} a_{i}a_{j}>(n-1)!\cdot\frac{1}{n}\iff \boxed{2\cdot\sum _{i\neq j} a_{i}a_{j}> \frac{n-1}{n}}$. Now notice that: $2\cdot\sum _{i\neq j} a_{i}a_{j}=\big{(}\sum _{i=1}^{n} a_{i}\big{)}^2-\sum _{i=1}^{n} a_{i}^2=1-\sum _{i=1}^{n} a_{i}^2\implies \boxed{\sum _{i=1}^{n} a_{i}^2<\frac{1}{n}}$, but that's a contradiction because $\sum _{i=1}^{n} a_{i}^2\geq\frac{1}{n}\cdot \big{(}\sum _{i=1}^{n} a_{i}\big{)}^2=\frac{1}{n}$, by the $QM\geq AM$ inequality, and we are done. $_{\blacksquare}$
12.11.2024 11:05
Nice global problem! (Although a bit standard) In the following, let $n = 2025$, and the numbers be $a_1, \dots, a_{2025}$. Assume FTSOC the statement doesnt hold. Sum over everything to get $$\frac{n^2 \times 2^n}{n\times \binom{n}{2} }\sum_{1 \le i < j \le 2025} a_ia_j > \frac{2^n}{n}$$$$\implies \sum_{1 \le i < j \le 2025} a_ia_j > \frac{n-1}{2n}.$$ Now we have $$\sum_{1 \le i \le 2025} a_i^2 = \left(\sum_{1 \le i \le 2025} a_i\right)^2 - 2 \sum_{1 \le i < j \le 2025} a_ia_j$$$$<1-\frac{n-1}{n} = \frac{1}{n}$$. But then $$\frac 1n > \sum_{1 \le i \le 2025} a_i^2 \stackrel{\rm QM-AM}{\ge} \frac{\left(\sum_{1 \le i \le 2025} a_i\right)^2}{n} = \frac 1n,$$contradiction. $\square$
20.01.2025 15:55
We can do this by many different ways... Let $P_1, P_2, ..., P_{2024!}$ be the $2024!$ different ways to arrange the numbers $x_1, x_2, ..., x_{2025}$ in a circle and let $S(P_i)$ be the sum of the product of it neighboring numbers. Note that the product $x_ix_j$ appears in exactly $2\cdot2023!$ permutations since we can consider the numbers $x_ix_j$ and $x_jx_i$ as one and permutate it over all the others $2023$ numbers. Therefore the mean of the $S(P_i)$s is $$\mathbb{M}=\frac{\sum_i S(P_i)}{2024!}=\frac{2\cdot2023!}{2024!}\sum_{i>j} x_ix_j=\frac1{1012} \sum_{i>j} x_ix_j$$But, by Cauchy-Schawrz we get that $$(x_1^2+x_2^2+...+x_{2025}^2)(1+1+...+1) \geq (x_1+x_2+...+x_{2025})^2=1$$$$(x_1+x_2+...+x_{2025})^2=x_1^2+x_2^2+...+x_{2025}^2+2\sum_{i>j} x_ix_j = 1 \geq \frac1{2025} +2\sum_{i>j}x_ix_j$$$$\frac{1012}{2025} \geq \sum_{i>j} x_ix_j \Rightarrow \frac1{2025} \geq \mathbb{M}$$So there must exist a permutation $P_i$ such that $S(P_i) \leq \frac1{2025}$ $\blacksquare$ ...To be more formal, if $P$ is a randomly and uniformly choosen permutation over the $P_i$s, note that $\mathbb{M}=\mathbb{E}[S(P)]$ and hence, for a infinitely small $\epsilon$, MarkovĀ“s inequallity says that $$\mathbb{P}(S(P) \geq \frac1{2025}+\epsilon) \leq \frac{\mathbb{E}[S(P)]}{\frac1{2025}+\epsilon} < 1$$So, again, there must exist a permutation $P_i$ such that $S(P_i) \leq \frac1{2025}$ $\blacksquare$