Let $n\geqslant 2$ be a positive integer and $a_1,a_2, \ldots ,a_n$ be real numbers such that \[a_1+a_2+\dots+a_n=0.\]Define the set $A$ by \[A=\left\{(i, j)\,|\,1 \leqslant i<j \leqslant n,\left|a_{i}-a_{j}\right| \geqslant 1\right\}\]Prove that, if $A$ is not empty, then \[\sum_{(i, j) \in A} a_{i} a_{j}<0.\]
Problem
Source: IMO 2019 SL A4
Tags: algebra, IMO Shortlist, IMO Shortlist 2019
23.09.2020 10:12
Because $\left(\sum a_i\right)^2=0$, it suffices to prove that $\sum_{\substack{(i,j)\\|a_i-a_j|<1}}a_ia_j>0$. This sum is equal to $$\sum_{i=1}^{n}a_i\left(\sum_{\substack{j,j\neq i\\|a_i-a_j|<1}}a_j\right)$$. If $|a_i|\geq 1$ then $a_ia_j>0$ for all $j$ which $|a_i-a_j|<1$ Now, let $b_1,b_2,\hdots,b_m$ be all elements of $a_1,a_2,\dots,a_n$ such that $|a_i|<1$, we are left to show that $\sum_{\substack{(i,j)\\|b_i-b_j|<1}}b_ib_j>0$ If $|b_i-b_j|\geq 1$, then $b_i,b_j$ must have different signs, so $\sum_{\substack{(i,j)\\|b_i-b_j|\geq 1}}b_ib_j<0$. Hence, $$\sum_{\substack{(i,j)\\|b_i-b_j|<1}}b_ib_j=\left(\sum_{i=1}^{m}b_i\right)^2-\sum_{\substack{(i,j)\\|b_i-b_j|\geq 1}}b_ib_j>0$$as desired.
23.09.2020 11:02
This was P2 on some Croatian IMO simulation. Here's my idea of how to solve it without much Latex. Sort the $a_i$ ascendingly and define $b_i$ as the sum of all $a_j$ such that $|a_j-b_i|<1$. We can assume that all numbers aren't $0$ since each $0$ does not change anything when removed and not every number is $0$. Similarly at least one of $b_1,b_n$ is not $0$ since $A$ isn't empty. We want the sum of $a_ib_i$ to be positive. I will partition that sum into intervals and show that the sum over each interval is positive. Take the indices $x,y,z$ as follows: $x$ is the boundary between negative and positive $a$s, $y$ is the boundary between negative and positive $b$s (WLOG $y \geq x$), $z$ is the boundary between $b_i$ which do not include positive $a$s in their definition and ones which do. $z\leq x \leq y$. Now we look at the sums of $a_ib_i$ from $1$ to $z$, from $z$ to $y$ and from $y$ to $n$. All of those sums are positive. The first one and last one are clearly positive since we're adding multiples where each multiple is a multiple of two numbers with the same sign, so they are all positive. For the middle sum, we notice that the $b_i$s are also ascendingly sorted since are taking away negative numbers and adding positive ones as $i$ grows. We now use Chebyshev or rearrangement or whatever to find that $\sum_{(z,y)}a_ib_i\geq\frac{\sum_{(z,y)}a_i\sum_{(z,y)}b_i}{n}$. The second of the two sums is clearly negative since all the $b_i$s are negative, whereas the first sum it can be gotten that it's less than the last negative $b$ (the defintion of the last negative $b$ contains a subset of negative $a$s and a superset of positive $a$s when comparing to $\sum_{(z,y)}a_i$), hence both of the sums are negative which means their multiple is positive so so the multiple is positive so $\sum_{(z,y)}a_ib_i$ is positive. We have a strict inequality within at least one (probably both idk) of $\sum_{(1,z)}a_ib_i$ and $\sum_{(y,n)}a_ib_i$ so we're done.
23.09.2020 11:12
??????????
23.09.2020 21:22
23.09.2020 21:33
https://dgrozev.wordpress.com/2020/09/23/imo-2019-shortlist-problem-a4/
26.09.2020 20:01
W.l.o.g. $a_i\neq0$ for $i=1,2,\cdots,n$. (If $A$ ist not empty, the maximum and minimum are positive and negative. So $A$ can not become empty by erasing zeros.) In the first step, we change the order of the $a_i$. If $\sum_{i=1}^ka_k\geq0$, choose $a_{k+1}$ from the remaining negative numbers as one with a minimal absolut value. If $\sum_{i=1}^ka_k<0$, choose $a_{k+1}$ from the remaining positive numbers as one with a minimal absolut value. (The condition $a_1+a_2+\cdots+a_n=0$ makes this possible.) If $a_k$ is positive, $a_k$ is the maximum of $\{a_1,a_2,\cdots a_k\}$. We have $a_1+a_2+\cdots,a_{k-1}<0$. If there is no index $i$ satisfying $a_i>0$ and $1\leq i<k$ and $|a_i-a_k|\geq1$, we have: \[ \sum_{\substack{1\leq i<k \\ |a_i-a_k|\geq1}}a_ia_k\leq0 \]If there is an index $i$ satisfying $a_i>0$ and $1\leq i<k$ and $|a_i-a_k|\geq1$, we have $|a_i-a_k|\geq1$ for any index $i$ satisfying $a_i<0$ and $1\leq i<k$. This implies: \[ \sum_{\substack{1\leq i<k \\ |a_i-a_k|\geq1}}a_ia_k<0 \]We get analogously \[ \sum_{\substack{1\leq i<k \\ |a_i-a_k|\geq1}}a_ia_k\leq0 \]for $a_k<0$. If $A$ is not empty, there are indices $i<k$ satisfying $|a_i-a_k|\geq1$. If $a_k$ is positive, there can not be equality in \[ \sum_{\substack{1\leq i<k \\ |a_i-a_k|\geq1}}a_ia_k\leq0 \]If $a_k$ is negative, there is equalitiy exactly if $a_1+a_2+\cdots a_{k-1}=0$. This implies $a_1+a_2+\cdots a_k<0$. The number $a_{k+1}$ has to exist and it has to be positive. This implies $|a_k-a_{k+1}|\geq1$ and \[ \sum_{\substack{1\leq i<k+1 \\ |a_i-a_{k+1}|\geq1}}a_ia_{k+1}<0 \]Finally we have that \[ \sum_{\substack{1\leq i<k \\ |a_i-a_k|\geq1}}a_ia_k\leq0 \]for $k=1,2,\cdots,n$ and there is a $k$ with \[ \sum_{\substack{1\leq i<k \\ |a_i-a_k|\geq1}}a_ia_k<0 \]Adding up over all $k$ gives: \[ \sum_{(i,j)\in A}a_ia_j=\sum_{k=1}^n\sum_{\substack{1\leq i<k \\ |a_i-a_k|\geq1}}a_ia_k<0 \]
29.09.2020 16:23
The inequality is equivalent to $$\sum_{\substack{(i,j)\\|a_i-a_j|<1}}a_ia_j>0$$(note that we sum over ordered pairs ). Assume that there are no $a_i=0$ and consider all the $a_i$ in $(-1,1):(-1,0)(0,1)$ , the $a_i$ outside $(-1,1)$ do not form negative terms in the sum and we just ignore them. If $a_i,a_j\in (-1,0) $ or $a_i,a_j\in (0,1)$ then the term $a_ia_j$ is inside the sum and if $a_i\in (-1,0)$ and $a_j\in (0,1)$ then these $a_ia_j$ are the only negative terms that might exist in the sum and we conclude that: $$\sum_{|a_i-a_j|}a_ia_j\ge \left( \sum_{a_i\in (-1,0)}a_i \right)^2 +\left( \sum_{a_i\in (0,1)}a_i \right)^2+\left( \sum_{a_i\in (-1,0)}a_i \right)\left( \sum_{a_i\in (0,1)}a_i \right)\ge 0$$
16.10.2020 20:32
Interesting. Much easier than A3?? Notice that $(a_1 + \ldots + a_n)^2 = 0 = \sum a_ia_j$ over all $n^2$ pairs $(i, j)$. Let $S$ denote the set of pairs $(i, j)$ such that $|a_i - a_j| < 1$. It suffices to show that for all pairs $(i, j) \in S$ (possibly equal), the sum\[\sum a_ia_j \geq 0.\]Note that it is possible to ignore all terms $a_k$ with $|a_k| \geq 1$ since all numbers $m$ that would form a pair with $k$ such that $|a_k - a_m| < 1$ must require $a_k, a_m$ being the same sign, and thus $a_ka_m$ adds positively to the sum. Now, we are left with terms with magnitude $< 1$, let them be $b_1, \ldots , b_{\ell}$. From the above we know that\[\sum_{|a_i - a_j| < 1} a_i a_j > \sum_{|b_i - b_j| < 1} b_ib_j\]and since all $b_i$ have magnitude $< 1$, that means that for all $k$, if some $b_m$ satisfies $|b_k - b_m| \geq 1$, then $b_k$ and $b_m$ have opposite signs and thus adding $b_kb_m$ decreases the sum. Hence, if the sum of all terms $b_ib_j$ with $|b_i - b_j| \geq 1$ is negative, and thus\[\sum_{|b_i - b_j| < 1} b_ib_j > \sum_{|b_i - b_j| < 1} b_ib_j + \sum_{|b_i - b_j| \geq 1} b_ib_j = (b_i + \ldots b_j)^2 \geq 0\]as desired. $\blacksquare$
06.11.2020 18:34
Let's do this the hard way (The above solutions, are much more cleaner, in my opinion -- though I missed the "squaring and homogenising" part; hence the longer solution.) For those who decided that direct computation is a good idea: Divide the whole set $S = \{a_1,a_2,\ldots,a_n\}$ of reals into four groups: the large and small negatives, and the large/small positives (while ignoring the zeroes because they're meaningless), \[ N_l = \{x \mid x < -1 \}, N_{s} = \{ x \mid -1 \leq x < 0 \}\]\[ P_l = \{x \mid x > 1 \}, P_s = \{ x \mid 0 < x \leq 1\} \]We are going to count the value of $\sum_{(i,j)\in A} a_ia_j$ = $\frac{1}{2}\sum_{|a_i-a_j| \geq 1} a_ia_j$ according to each $a_i$ (the front term), cycling one-by-one from the terms in $N_l$ and $P_l$ into $N_s$ and $P_s$, \begin{align*} \sum_{j, |n_l - a_j| \geq 1} n_l a_j & \leq \sum_{j} n_l a_j \\ &\leq n_l \cdot (-n_l) = -n_l^2. \end{align*}Summing through all $n_l$ and $p_l$ (if indeed they are nonempty) -- we get \[ \sum_{\substack{|a_i-a_j| \geq 1 \\ a_i \in N_l \cup P_l}} a_ia_j \leq - \sum_{a \in N_l \cup P_l} a^2\]However, the $a_i$ in the "small sets" needs to be handled more delicately. The important observation preceding the computation is that each $a_i$ in, say $N_s$, cannot make $\textbf{too much positive terms}$, where it can only do so with terms from $N_l$, whence it $\textbf{must make LARGE negative terms}$ with $\textbf{ALL}$ terms of $P_l$. Formally, as we fix a $a_i = n_s$, and summing through all $n_s$ and $p_s$, we get: \begin{align*} \sum_{j,|n_s-a_j| \geq 1} n_s a_j &\leq \sum_{j, a_j \in N_l \cup P_l} n_sa_j, \\ &\leq n_s (-\sum_{a_j \in N_s \cup P_s}a_j),\\ \sum_{\substack{a_i \in N_s \cup P_s \\ |a_i - a_j| \geq 1}} a_ia_j &\leq -(\sum_{a\in N_s \cup P_s}a)^2 \end{align*}And we are done with the problem. Note that equality cannot be attained as the two statements "$N_l \cup P_l$ nonempty" (equality on first ineq) and "there does not exist $a_i \in N_s, a_j \in P_s$ so that $|a_i-a_j| \geq 1$" (the terms we throw out on the second ineq) cannot be true simultaneously, making the right hand side definitely negative.
17.11.2020 11:52
Using \((a_1+\cdots+a_n)^2=0\) the desired inequality rewrites as \[\sum_{\substack{1\le i,j\le n\\ |a_i-a_j|<1}}a_ia_j>0.\]Each \(|a_i|\ge1\) will only produce positive terms on the left, so assume \(|a_i|<1\) for all \(i\). (We drop the condition \(a_1+\cdots+a_n=0\).) Then \(a_ia_j<0\) whenever \(|a_i-a_j|\ge1\), so \[\sum_{\substack{1\le i,j\le n\\ |a_i-a_j|<1}}a_ia_j>\sum_{1\le i,j\le n}a_ia_j=(a_1+\cdots+a_n)^2\ge0.\]
02.01.2022 06:56
Since $(a_1+a_2+\dots+a_n)^2 = 0$, it is sufficient to prove that $$\sum _{|a_i-a_j| \leq 1} a_i a_j > 0.$$Clearly if $|a_i| \geq 1$ then all of the appearances of $a_i$ in the summation will be non-negative, so by deleting all such $a_i$ assume that $|a_i| < 1$ for all $i$. But note that if $|a_i-a_j| > 1$ then $a_ia_j$ must be negative, so $$\sum _{|a_i-a_j| > 1} a_i a_j < 0$$as desired.
31.03.2022 20:00
We can assume $a_i \neq 0 $ for all $i$. Let \[B=\left\{(i, j)\,|\,1 \leqslant i,j \leqslant n,\left|a_{i}-a_{j}\right| < 1\right\}\]Then it is sufficient to prove that, \[\sum_{(i, j) \in B} a_{i} a_{j}\ge 0\]Let \[C=\left\{ i \,|\, 1 \leqslant i \leqslant n \,,\, -1 <a_i<1 \right\} \]\[C_1=\left\{ i \,|\, 1 \leqslant i \leqslant n \,,\, -1 <a_i<0 \right\} \]\[C_2=\left\{ i \,|\, 1 \leqslant i \leqslant n \,,\, 0 <a_i<1 \right\} \]Then, $\sum_{(i, j) \in B} a_{i} a_{j}\ge \sum_{(i, j) \in C_1 \times C_1} a_{i} a_{j} + \sum_{(i, j) \in C_2 \times C_2} a_{i} a_{j} + 2\sum_{(i, j) \in C_1 \times C_2} a_{i} a_{j} = \sum_{(i, j) \in C \times C} a_{i} a_{j} = (\sum_{i \in C} a_{i})^2 \ge 0. \, \blacksquare$
09.07.2022 14:03
13.01.2023 17:32
Here is my solution: https://calimath.org/pdf/ISL2019-A4.pdf And I uploaded the solution with motivation to: https://youtu.be/jGNkXNoto_U
18.02.2023 14:58
Define $B=\left\{(i,j)\mid 1\leqslant i,j\leqslant n,|a_i-a_j|\geqslant 1\right\},C=\left\{(i,j)\mid 1\leqslant i,j\leqslant n,|a_i-a_j|< 1\right\}.$ $\because \sum_{(i, j) \in A} a_{i} a_{j}=\frac 12\sum_{(i, j) \in B} a_{i} a_{j}=\frac 12\left(\sum\limits_{i=1}^na_i\right)^2-\frac 12\sum_{(i, j) \in C} a_{i} a_{j}=-\frac 12\sum_{(i, j) \in C} a_{i} a_{j}.$ We only need to prove $\sum_{(i, j) \in C} a_{i} a_{j}>0.$ Define $P=\left\{i\mid a_i\leqslant -1\right\},Q=\left\{i\mid -1<a_i\leqslant 0\right\},R=\left\{i\mid 0<a_i< 1\right\},S=\left\{i\mid a_i\geqslant 1\right\}.$ Then $\sum_{(i, j) \in C} a_{i} a_{j}\geqslant \sum_{i\in P\cup S}a_i^2+\sum_{(i,j)\in Q\cup R}a_ia_j=\sum_{i\in P\cup S}a_i^2+\left(\sum_{i\in Q\cup R}a_i\right)^2\geqslant 0.$
27.02.2023 07:13
Consider the following types of pairs. Let $A$ be the set of pairs $(i,j)$ such that $|a_i-a_j|\ge 1$ and $|a_i|,|a_j|\le 1$. Let $B$ be the set of pairs $(i,j)$ such that $|a_i-a_j| \le 1$ and $|a_i|,|a_j|\le 1$. Let $C$ be the set of pairs $(i,j)$ such that $|a_i-a_j|\ge 1$ and $|a_i|$ or $|a_j|\ge 1$. Let $D$ be the set of pairs $(i,j)$ such that $|a_i-a_j|\le 1$ and $|a_i|$ or $|a_j|\ge 1$. Let $S(X)$ be the value of \[\sum_{(i, j) \in S} (a_{i} a_{j})\]We wish to analyze the value of $S(A)+S(C)$ and prove that it is negative. Note that $S(A)+S(B)+S(C)+S(D)=0$. Thus, we just need to show $S(B)+S(D)>0$. Look at $S(D)$. Without loss of generality, assume $|a_i|\ge 1$ and so $a_i$ and $a_j$ are same sign. Thus, $S(D)>0$. Now, look at $S(A)$. If $a_i$ and $a_j$ are same sign then $|a_i-a_j|$ cannot be at least one. Thus, $a_ia_j<0$ so $S(A)<0$. Note that $a_i(a_1+a_2+\dots + a_{i-1}+a_i+a_{i+1}+\dots+a_{n})=0$ so $S(C)<0$ which means $S(A)+S(C)<0$ as desired.
07.03.2023 11:55
Note that since $2 \sum_{(i,j) \in A} a_ia_j + \sum_{|a_i - a_j| < 1} a_ia_j = (a_1 + a_2 + \cdots + a_n)^2 = 0$, it suffices to show that the second sum is positive, given $A$ is nonempty. Let $X$ be the set of all $a_i$ that are between $-1$ and $1$. Consider all elements of the second sum which contain both elements in $X$. The rest of the terms are clearly positive since $xy > 0$ for $x \geqslant 1$ and $|x-y| < 1$. This sub-sum is at least $\left(\sum_{i \in X} a_i \right)^2$ since this includes even more negative terms than earlier, and this is at least zero. But note that for equality to hold, all numbers $i = 1,2,\cdots,n$ must be in $X$, as well as every pair of opposite signs must be included. But this means that if $M$ and $m$ are the largest and smallest terms, then $1 > M > 0 > m > -1$ and $M - m < 1$. However, in this case $A$ is empty and so can be ignored. So in all cases when $A$ is nonempty, we have that $\sum_{(i,j) \in A} a_ia_j < 0$, as desired.
30.07.2023 04:45
legit trolling Since $a_1+\cdots+a_n=0$, by squaring and subtracting it suffices to show that $$\sum_{\substack{1 \leq i,j \leq n\\|a_i-a_j|<1}} a_ia_j>0$$whenever the left-hand summation doesn't contain every $1 \leq i,j \leq n$. Drop the condition $a_1+\cdots+a_n=0$ and additionally suppose that $a_1 \leq \cdots \leq a_n$. Clearly $a_1$ must be negative and $a_n$ must be positive, otherwise we are done. WLOG suppose that $a_2+\cdots+a_{n-1} \geq 0$. Then because $|a_1-a_n|\geq 1$, when we delete $a_n$ the sum decreases by $$a_n(a_n+2a_{n-1}+2a_{n-2}+\cdots+2a_j) \geq 2a_n(a_{n-1}+\cdots+a_j)\geq 2a_n(a_{n-1}+\cdots+a_2) \geq 0,$$where $j\geq 2$ is the least integer with $|a_n-a_j|<1$, hence we are done by downwards induction. $\blacksquare$
08.01.2024 21:15
xooks rbo. Thought of this idea initially but didnt think it would work. Asked for a hint and turns out it works. Oh well :/ We prove this claim which implies the problem Claim: The following inequality holds with equality when $A$ is empty. \[\sum_{\substack{1\leq i,j \leq n \\ |a_i-a_j|<1}}a_ia_j\geq 0\]Proof. The only negative terms from this sum come when $a_i,a_j \in [-1,1]$. Thus we calculate \[\sum_{\substack{-1\leq a_i,a_j\leq 1 \\ |a_i-a_j|<1}}a_ia_j=\left(\sum_{-1\leq a_i\leq 1}a_i\right)^2- \sum_{\substack{-1\leq a_i,a_j\leq 1 \\ |a_i-a_j|\geq 1}}a_ia_j.\]The first summ is clearly nonnegative by trivial inequality and the second sum is also nonnegative since each summand is a positive number times a negative number. This implies that \[\sum_{\substack{-1\leq a_i,a_j\leq 1 \\ |a_i-a_j|<1}}a_ia_j\geq 0\]and the other terms in \[\sum_{\substack{1\leq i,j \leq n \\ |a_i-a_j|<1}}a_ia_j\]not in the $[-1,1]$ sum are between two numbers that have the same sign. It is easy to see equality holds when $A$ is empty, proving the claim. $\blacksquare$ The conclusion follows as \[2\sum_{(i, j) \in A} a_{i} a_{j}=\left(\sum_{i=1}^n a_i\right)^2-\sum_{\substack{1\leq i,j \leq n \\ |a_i-a_j|<1}}a_ia_j= 0-\sum_{\substack{1\leq i,j \leq n \\ |a_i-a_j|<1}}a_ia_j<0\]
18.01.2024 05:01
Because $\left(\sum a_i\right)^2=0$, it suffices to prove that $\sum_{\substack{(i,j)\\|a_i-a_j|<1}}a_ia_j>0$ where $ 1 \leqslant i \leqslant j \leqslant n $ The case for $|a_i|\geq 1$ is trivial. Lets consider the case for $|a_i|<1$ Let $p_1,p_2,\dots,p_k$ be numbers in the range $(0,1)$ and let $ -q_1,-q_2,\dots,-q_m$ be numbers in the range $ (-1,0)$ Observe that $\left(\sum p_i\right)^2 $ $+$ $\left(\sum -q_i\right)^2$ = $\left(\sum p_i\right)^2 $ $+$ $\left(\sum q_i\right)^2$ $\geq$ $2 [\left(\sum p_i\right) \left(\sum q_i\right)]$ Since $2 [\left(\sum p_i\right) + \left(\sum q_i\right)]$ $+$ $\left(\sum p_i\right)$$\left(\sum -q_i\right)$ $>0$ We are done
20.01.2024 13:05
y-is-the-best-_ wrote: Let $n\geqslant 2$ be a positive integer and $a_1,a_2, \ldots ,a_n$ be real numbers such that \[a_1+a_2+\dots+a_n=0.\]Define the set $A$ by \[A=\left\{(i, j)\,|\,1 \leqslant i<j \leqslant n,\left|a_{i}-a_{j}\right| \geqslant 1\right\}\]Prove that, if $A$ is not empty, then \[\sum_{(i, j) \in A} a_{i} a_{j}<0.\] First of all by the problem condition that $a_1+a_2+....a_n=0$ we know that: \[(a_1+a_2+.....a_n)^2=\sum_{1 \leq i,j \leq n}{a_ia_j}=0\] it's suffix to show that: \[\sum_{i,j \in B}{a_ia_j} > 0\](1) Where $B= \{ (i.j) | 1 \leq i.j \leq n, |a_i-a_j|<1 \} $ Now if $|a_i| \geq 1$ then it can only produce non-negative values in (1). The reason is that if $|a_i| \leq 1$ and $|a_i-a_j| < 1$, then if $a_i$ is negative then so is $a_j$ (as if it's not, then $|a_i-a_j| \geq 1$). Now if $a_i$ is positive then $a_j$ must be positive too (as if it's negative then $|a_i-(-|a_j|)|=|a_i+a_j| \geq 1$). Now let $c_1,...c_k$ be a sequence such that $|c_i|<1$ for all $1\leq i \leq k$. We also know that \[\sum_{i,j \in B} a_i a_j > \sum_{|c_i - c_j| < 1} c_ic_j\] And since $|c_i|<1$, we have that $ |c_i-c_j| \geq 1 $ means that $c_i,c_j $ have opposite signs. Meaning that $c_ic_j$ is negative. and thus \[\sum_{|c_i - c_j| < 1} c_ic_j > \sum_{|c_i - c_j| < 1} c_ic_j + \sum_{|c_i - c_j| \geq 1} c_ic_j = (c_i + \ldots c_j)^2 \geq 0\]
22.01.2024 03:51
First realize that $\left(\sum_{i=1}^n a_i \right)^2 = 2\sum_{(i,j) \in A} a_ia_j + \sum_{\substack{1\le i, j \le n \\ |a_i - a_j| < 1} } a_ia_j$. So we want to show $$\sum_{\substack{1\le i, j \le n \\ |a_i - a_j| < 1} } a_ia_j >0$$. However, notice that if $|a_i|\ge1$, then $a_ia_j>0$ in the sum above. So WLOG we can assume that $|a_i| < 1$. Now note that if we have $|a_i - a_j|\ge1$, then we have $a_ia_j < 0$. So we get that $$\sum_{\substack{1\le i < j \le n \\ |a_i - a_j| < 1} } a_ia_j > \sum_{1 \le i, j \le n} a_i a_j \ge 0$$and we are done.
22.04.2024 13:56
For each $1 \leq i \leq n$ define $S_i = \sum_{\substack{1 \leq j \leq n \\ |a_i-a_j|<1}}a_ia_j$. Since $(a_1+a_2+ \dots + a_n)^2=0$, it suffices to show that \[S_1+S_2+ \dots + S_n = (a_1+a_2+ \dots + a_n)^2 - 2 \sum\limits_{(i,j) \in A}a_ia_j >0\]Consider $i$ such that $|a_i| \geq 1$. Observe that each $a_j$ such that $|a_i-a_j|<1$ has the same sign as $a_i$ and hence $a_ia_j \geq 0$. This implies that $S_i \geq 0$. Let $-1 < a_i \leq a_{i+1} \leq \dots \leq a_k \leq 0 \leq a_{k+1} \leq a_{k+2} \leq \dots \leq a_j < 1$. The previous paragraph implies that, it suffices to show that $S_i+S_{i+1}+ \dots S_j > 0$. Let $x=a_i+\dots+a_k$ and $y=a_{k+1}+\dots+a_j$. Consider $i \leq \alpha \leq k$. Observe that all of the numbers $a_i, a_{i+1}, \dots, a_{j}$ are contained in the set $\{a_{\beta} \mid |a_{\alpha}-a_{\beta}|<1\}$ whilst no number greater than $a_j$ is contained in it. This implies that \[S_{\alpha} \geq a_{\alpha}(a_i+\dots+a_k-a_{k+1}-\dots-a_j)=a_{\alpha}(x-y)\]With the same reasoning we get that for each $k+1 \leq \alpha \leq j$, \[S_{\alpha} \geq a_{\alpha}(a_{k+1}+\dots+a_j-a_i-\dots-a_j)=a_{\alpha}(y-x)\]Summing up these inequalities we get \[S_i+\dots+S_j \geq x(x-y)+y(y-x) = (x-y)^2 > 0 \](The inequality is strict because $x$ and $y$ have different signs.)
01.06.2024 23:31
Divide all numbers into two categories: positives and negatives (forget about zeros, they make no change to the problem statement). Let $a_1<\ldots<a_t$ be positives and $-b_1>\ldots>-b_s$ be negatives. Let $m$ be the largest integer such that $a_m-a_1<1$ (obviously it exists), and $M$ be the largest integer such that $b_M-b_1<1$. Now we want to make bounds on the sum of Positive-Negative multiplication and Sign-Same Sign multiplication. Speaking about former, $|Pos-Neg| \geq (a_{m+1}+\ldots+a_t)(b_{M+1}+\ldots+b_s)+(a_{m+1}+\ldots+a_t)(b_1+\ldots+b_M)+(a_1+\ldots+a_m)(b_{M+1}+\ldots+b_s)$. Let's define $a_1+\ldots+a_t=b_1+\ldots+b_s=S$, $a_{m+1}+\ldots+a_t=S_a$, $b_{M+1}+\ldots+b_s=S_b$. Then our estimation rewrites as $S_aS_b+S_a(S-S_b)+S_b(S-S_a)=S_aS+S_bS-S_aS_b$. Now let's estimate Sign-Same sign multiplication as $$Sgn-Sgn \leq S_a(S-S_a)+S_b(S-S_b)+\sum_{i>j \geq m+1} a_ia_j + \sum_{i>j \geq M+1} b_ib_j = SS_a+SS_b-S_a^2-S_b^2+\frac{S_a^2+S_b^2-\sum_{i} a_i^2-\sum_{i} b_i^2}{2}=SS_a+SS_b-\frac{S_a^2+S_b^2+\sum_{i} a_i^2+\sum_{i} b_i^2}{2}$$Our goal is to show $|Pos-Neg|>|Sgn-Sgn|$, so now we just need to check that $SS_a+SS_b+\frac{S_a^2+S_b^2+\sum_{i} a_i^2+\sum_{i} b_i^2}{2}-S_aS_b>SS_a+SS_b$ $(S_a-S_b)^2+\sum_{i} a_i^2+\sum_{i} b_i^2>0$ If this is not true, then $a_i=0$ for $i \geq m+1$ and $b_i=0$ for $i \geq M+1$, so $m=t, M=s$. But in this case there are no same sign multiplications, which immediately gives us the desired.
12.06.2024 09:26
combo solution... kinda sussy man. Basically let the largest negative one be $a_i$ and the smallest positive one be $a_j$ , then let one of their magnitudes be greater, WLOG the negative one (because flipping all signs doesn't change anything!). so then send $a_i$ -> $a_i + a_j$, $a_j $-> $0$, I claim this does not decrease the value. of the summation. Consider all the terms in the summation. If an $a_ia_j$ term exists it either gets deleted or sent to zero, and the term must initially be negative. so that's an increase. Then all terms that don't contain $a_i$ and $a_j$ don't matter. so then consider $a_k$ for some $k$. if both $a_ka_i$ and $a_ka_j$ exist, then they will both exist after the transformation and thus don't matter since the sum of both terms is still the same. If only one exists, we do case work. If $a_ka_i$ exists and not $a_ka_j$, then $a_k> 0$ it doesn't matter if $a_ka_j$ exists after the transformation since its gonna be zero anyways, and then $a_ka_i$ either stops existing due to distance getting closer or ends up increasing. In the other case where $a_ka_j$ exists but not $a_ka_i$, $a_k < 0$, so $a_ka_j$ is originally negative and then goes to zero or stops existing, and then $a_ka_i$ goes from not existing to either not existing or being positive, so everything in every case is a net increase and you are done. Now this algorithm must terminate since you keep sending stuff to zero. Now we prove at least one state eventually reached by the algorithm is negative if the gap between $a_{max}$ and $a_{min}$ is at least one. Consider the value with the greatest magnitude, let it be $a_{max}$ and WLOG let it be positive. $a_{max}$ is never affected by the algorithm until it is the only positive value. Now also $a_{min}$ would only ever be affected if it was the only negative value left, which would imply that at some point the sum of the positive values has the same magnitude as $a_{min}$, which doesn't happen since $a_{max}$ just has a greater magnitude. as a result $a_{max}- a_{min}$ is still at least one when there is only one positive value since neither changed. Now clearly the value of the summation is negative since for each negative $a_x$, if it is far enough away from any other negative $a_x$, it must also be far enough away from $a_{max}$. Assume otherwise, if $a_x$ is greater than desired far enough negative its also far enough away from $a_{min}$, but $a_{min}$ is closer to $a_x$ than $a_{max}$ since $a_{min}$ is closer to $0$ than $a_{max}$ and you just go down from $0$. if it is less than said value, then its obviously further to $a_{max}$ since you are just going further in the same direction. so for each $a_i$, the sum of terms that contain $a_i$ are nonpositive, and at least one term is known to be negative so you are done.
29.08.2024 09:17
Let $S = \{i \; | \; 1 \leq i < j\leq n, a_i \in (-1, 1)\}$. Then $$ 0 \leq (\sum_{i \in S} a_i)^2 = \sum_{i \in S} a_i^2 + 2\sum_{i, j \in S, i<j} a_ia_j \leq \sum_{1 \leq i \leq n} a_i^2 + 2 \sum_{(i,j) \notin A} a_ia_j$$ the final inequality hold, since any positive summand in L.H.S. $a_ia_j > 0$ with $a_i, a_j \in (-1, 1)$ with same sign $\implies |a_i-a_j| < 1$, i.e. $(i, j) \notin A$. On the other hand, a negative summand R.H.S. $a_ia_j < 0$ with $(i, j) \notin A \implies |a_i - a_j|<1$, giving both $a_i, a_j \in (-1, 1)$ or $i, j \in S$. But $$ \sum_{1 \leq i \leq n} a_i^2 + 2 \sum_{(i,j) \notin A} a_ia_j + 2\sum_{(i, j) \in A} a_ia_j = (\sum_{1 \leq i \leq n} a_i)^2 = 0,$$giving $\sum_{(i, j) \in A} a_ia_j \leq 0$ as desired. Equality holds when $a_i \neq 0 \implies i \in S$ (with $a_i = 0 \implies i \in S$ too) and that $i, j \in S, i<j \iff (i,j) \notin A$ whenever $a_i \neq 0 \neq a_j$. That is, for any nonzero term $a_i, a_j$ with $i<j$, $(i,j) \notin A$. This leaves out the case that, say, $a_i = 0$, but since all $j \in S$, we have that $|a_i - a_j| < 1$, so $(i,j) \notin A$ either way. So the only equality case is when $A$ is empty, as desired.
14.01.2025 00:10
The case $n=2$ is trivial, as it implies $-x^2<0$ for $|x|\geq1$. Assume $n\geq3$. We prove assuming all numbers distinct and non-zero, and the idea may be easily generalized. We use the idea of scaling. Represent the points on the number line. WLOG assume $a_1<a_2<\cdots<a_n$. Then, we scale the numbers such that $|a_1-a_n|\geq1$ but all other differences are less than $1$. As a result, $A=\{1,n\}$. Clearly, $a_n>0$ and $a_1<0$, which means $a_1a_n<0$. We now scale the numbers such that the first few largest differences are bigger than 1 and we will have to prove the required result. Hence, it is equivalent to show that for any pair $(i',j')$ consider all pairs $(i,j)$ such that $|a_i-a_j|>|a_i'-a_j'|$, then $\sum a_ia_j<0$. Refer this sum to as $f(i',j')$. Order the differences in descending order. Let $(i_1,j_1)$ be the pair for which $f(i_1,j_1)$ attains its maximum value. If $f(i_1,j_1)<0$, then we are done. So, assume $f(i_1,j_1)\geq0$. Note that $a_{i_1}a_{j_1}>0$ must be true. Note that if $|a_{i_2}-a_{j_2}|,|a_{i_3}-a_{j_3}|,|a_{i_4}-a_{j_4}|$ are the differences just smaller than $|a_{i_1}-a_{j_1}|$, then we must have $a_{i_2}a_{j_2}<0$, $a_{i_3}a_{j_3}<0$, and so on. Suppose it so happens WLOG that $a_{i_2},a_{i_3}$ are positive. Then, $|a_{i_2}-a_{i_3}|<\max\{|a_{i_2}-a_{j_2},a_{i_3}-a_{j_3}\}$, but $a_{i_2}a_{i_3}>0$, which contradicts minimality. Hence, $i_3,j_3,i_4,j_4$, etc. must not exist. In fact, a similar argument gives that $(a_{i_1}-a_{i_2})(a_{j_1}-a_{j_2})=0$. Finally, we may take $a_{i_1}=a_{i_2}$. Note that this means $|a_{i_1}-a_{j_2}|$ is the least possible difference. Moreover, \[0\leq f(i_1,j_1)=f(i_1,j_2)-a_{i_1}a_{j_2}=-\frac{1}{2}\sum_{i=1}^{n}a_i^2-a_{i_1}a_{j_2}\]\[\Longrightarrow \frac{a_{i_1}^2+a_{j_2}^2}{2}\geq|\max\{a_i<0\}\min\{a_i>0\}|\geq\frac12\sum_{i=1}^{n}a_i^2,\]which fails for $n\geq3$. $\blacksquare$