Let $a_{i}$ and $b_{i}$, where $i \in \{1,2, \dots, 2005 \}$, be real numbers such that the inequality $(a_{i}x-b_{i})^{2} \ge \sum_{j=1, j \not= i}^{2005} (a_{j}x-b_{j})$ holds for all $x \in \mathbb{R}$ and all $i \in \{1,2, \dots, 2005 \}$. Find the maximum possible number of positive numbers amongst $a_{i}$ and $b_{i}$, $i \in \{1,2, \dots, 2005 \}$.
Problem
Source: Bulgarian IMO TST 2005, Day 2, Problem 1
Tags: inequalities, function, quadratics, inequalities proposed
22.12.2013 20:51
Denote $n=2005$, $A=\sum_{i=1}^n a_i$, $B=\sum_{i=1}^n b_i$. The inequality $(a_ix-b_i)^2\ge \sum_{j\neq i} a_jx-b_j$ can then be rewritten to $a_i^2x^2-2a_ib_ix+b_i^2\ge (A-a_i)x-(B-b_i)$, \[a_i^2 x^2-(2a_ib_i+A-a_i)x+(b_i^2+B-b_i)\ge 0.\quad(1)\] If $a_i=0$ for some $i=1,2,\dots,n$, then in $(1)$ the left-hand side cannot be a linear function of $x$, so $2a_ib_i+A-a_i=0$ as well, using $a_i=0$ this becomes $A=0$. Thus $(1)$ reduces to $b_i^2-b_i+B\ge 0$, which holds if $b_i$ is large enough. The point is, if $a_i=0$, then $(1)$ holds iff $A=0$ and $b_i$ is large enough, and in that case, even if we choose all $b_i$ positive, there must be at least two non-positive $a_i$. Assuming none of the $a_i$ are zero, $(1)$ is a quadratic inequality with leading coefficient $a_i^2>0$, hence it holds $\forall x\in\mathbb{R}$ iff its discriminant isn't positive, i.e. \[(2a_ib_i+A-a_i)^2\le 4a_i^2(b_i^2+B-b_i)\] \[4a_i^2b_i^2+4a_ib_i(A-a_i)+(A-a_i)^2\le 4a_i^2b_i^2-4a_i^2b_i+4a_i^2B\] \[4a_iAb_i\le 4a_i^2B-(A-a_i)^2.\quad (2)\] Now that we have given this equivalent condition, note that if $A=0$ such that $a_i>0$ for $i=2,3,\dots,n$ and $a_1=-\sum_{j=2}^n a_j$, moreover we choose $B$ so that $0\le 4a_i^2B-a_i^2$ $\forall i=1,2,\dots,n$ (take $B=\frac14$ for example), we have given a sequence of $a_i$ and $b_i$ reals with only one of them not positive, and this is $a_1$. On the other hand, if all $a_i$ are positive, we may divide $(2)$ by $4a_iA$ to get \[b_i\le \frac{a_i}A\cdot B-\frac{(A-a_i)^2}{4a_iA},\] summing these up for $i=1,2,\dots,n$ we get \[B\le 1\cdot B-\sum_{i=1}^n\frac{(A-a_i)^2}{4a_iA},\] \[\sum_{i=1}^n\frac{(A-a_i)^2}{4a_iA}\le 0,\] which is only possible if $A-a_i=0$ $\forall i$, which implies $a_1=a_2=\dots=a_n=0$. This is a contradiction, so we can have at most $2n-1=4009$ positive numbers $a_i$ and $b_i$.