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, \sum_{i=1}^K b_i, \sum_{i=1}^K c_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}

The following example shows that the absolute value and the sum is necessary: \begin{align*} a_1 = 1/2 + \epsilon, \quad &a_2 = \epsilon^2, \\ b_1 = 1/2 + \epsilon + \epsilon^2, \quad &b_2 = 0, \\ c_1 = 0, \quad &c_2 = 1/2 + \epsilon + \epsilon^2, \\ d_1 = 0, \quad &d_2 = 0. \end{align*}

Note that the following case is easy: if we have an explicit lower bound $b_i \ge c > 0$ for all $i$, then let $j$ be the index that maximizes $c_i/d_i$, then \begin{equation} a_j / b_j = c_j/d_j \ge (\sum_i c_i)/(\sum_i d_i) \ge 1 + \epsilon. \end{equation} Hence \begin{equation} a_i - b_i \ge c\epsilon. \end{equation} Similarly if we have a lower bound for $c_i$. Note that in these cases we don't even need the assumption that $\sum_i a_i \ge 1/2 + \epsilon$.

  • $\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$ – Iosif Pinelis 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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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