Let $n>1$ be an integer. For each numbers $(x_1, x_2,\dots, x_n)$ with $x_1^2+x_2^2+x_3^2+\dots +x_n^2=1$, denote $m=\min\{|x_i-x_j|, 0<i<j<n+1\}$ Find the maximum value of $m$.
Problem
Source: Rioplatense Olympiad 2001 P3
Tags: combinatorics, algebra
14.10.2017 02:09
Any idea??
11.04.2022 09:17
11.04.2022 18:28
WLOG $x_1 \leq x_2 \leq \cdots \leq x_n$. Let $$m=\min\{x_n-x_{n-1}, \dots ,x_3-x_2, x_2-x_1 \}$$Clearly we have to find the maximum of $m$. Note that $$n = n \sum x_i ^2 \geq n \sum x_i^2-(\sum x_i)^2 = \sum_{1 \leq j<i \leq n} (x_i-x_j)^2$$But we have $(x_i-x_j)^2 \geq (i-j)^2 m^2$, so we get $$n \geq m^2(\sum_{1 \leq j <i \leq n}(i-j)^2)=m^2 \cdot \frac{n^2(n-1)(n+1)}{12}$$which gives $$\boxed{m \leq \sqrt{\frac{12}{n(n-1)(n+1)}}}$$Equality holds when $x_i$ is an AP with sum $0$ and common difference $m$.
11.04.2022 20:20
Also possible by smoothing. Assume $x_1\le \dots \le x_n$. Think of $(x_i)$'s as points on the real line (not formal but easy to explain). Suppose that there's some $k$ with $m \le x_k-x_{k-1}$. The idea is to close the gap between $x_k$ and $x_{k-1}$ while making $x_1^2+x_2^2+\dots+x_n^2$ smaller. Consider some cases: If 0 lies left of $x_{k-1}$, then move $x_k,\ldots,x_n$ to the left by a distance of $(x_k-x_{k-1})-m$. If 0 lies right of $x_k$, move $x_1,\ldots,x_{k-1}$ to the right by a distance of $(x_k-x_{k-1})-m$. If 0 lies middle of $x_{k-1}$ and $x_k$, then do both of the things above at the same time, but while mantaining 0 between $x_{k-1}$ and $x_k$. We've made $x_k-x_{k-1}=m$ and we've also reduced $x_1^2+x_2^2+\dots+x_n^2$. (as we reduced absolute value of all moved numbers, and left the rest numbers with the same absolute value they had). Now multiply each $x_i$ by $(x_1^2+\dots+x_n^2)^{-1}>1$, making $m$ bigger. One keeps repeating this procedure until $x_2-x_1=x_3-x_2=\dots=x_n-x_{n-1}$, so $(x_i)$ is an arithmetic progression. Now one can finish like the other posts did, by showing that this arithmetic progression must have sum 0.