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.

| cite | improve this answer | |

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.