Consider four sequences of numbers, $0 \le a_i, b_i, c_i, d_i \le 1$, suppose they satisfy the following constraints:

(1). $\sum_{i=1}^K a_i \ge 1/2 + \epsilon$;

(2). $\sum_{i=1}^K d_i \le 1/2 - \epsilon$;

(3). $a_i d_i = b_i c_i$ for all $i=1, \ldots, K$.

Is it true that \begin{equation} \sum_{i=1}^K (|a_i - b_i| + |a_i - c_i|) = \Omega(\epsilon) ? \end{equation}

Added remark after seeing the answer: Initially my Condition (1) was, (1). $\sum_{i=1}^K a_i, \sum_{i=1}^K b_i, \sum_{i=1}^K c_i \ge 1/2 + \epsilon$. But it turns out (see the answer below) that the inequality is true even without the requirement on b_i and c_i.

  • $\begingroup$ There is no $d_i$ in that sum: did you mean that, or is it a mistake? Also, are the various conditions understood to hold for all $K \in \mathbb N$ (and the sequences to be infinite), or is $K$ fixed? $\endgroup$
    – Alex M.
    Sep 21 '18 at 15:47
  • $\begingroup$ Even though this problem has a pretty simple solution, I think it is nontrivial and somewhat intriguing. So, I don't understand the down vote. $\endgroup$ Sep 21 '18 at 17:38


It is not hard to show (see the proof at the end of this answer) that for any real $a,b,c,d\ge0$ such that $ad=bc$ we have \begin{equation}\tag{1} |a-b|+|a-c|\ge a-d. \end{equation} Replacing here $a,b,c,d$ by $a_i,b_i,c_i,d_i$ and summing in $i$, we have \begin{equation} \sum_i (|a_i - b_i| + |a_i - c_i|)\ge\sum_i a_i-\sum_i d_i\ge2\ep, \end{equation} as desired. (The conditions that $\sum_i b_i, \sum_i c_i \ge 1/2 + \ep$ were not needed or used here.)

Proof of (1). If $a=0$, then $a-d\le0$, so that (1) holds. So, without loss of generality (wlog), $a>0$, whence $d=bc/a$ and $a-d=(a^2-bc)/a$. So, wlog $a^2>bc$ and hence $a\ge b\wedge c$. Also, wlog $c\le b$. So, one of the following two cases takes place.

Case 1: $0\le c\le b\le a$. Here (1) can be rewritten as $$f(a,b,c):=a-b-c+bc/a\ge0,$$ which follows because $f(a,b,c)$ is nonincreasing in $b$ (given that $c/a\le1$) and hence $f(a,b,c)\ge f(a,a,c)=0$. So, (1) holds in Case 1.

Case 2: $0\le c\le a\le b$. Here (1) can be rewritten as $$g(a,b,c):=b-c+bc/a-a\ge0,$$ which follows because $g(a,b,c)$ is nondecreasing in $b$ and hence $g(a,b,c)\ge g(a,a,c)=0$. So, (1) holds in Case 2 as well.

Inequality (1) is completely proved.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.