Let $a_{i}, b_{i}, c_{i},\ d_{i}$ be non-negative sequences of length $k$ such that

$$ \begin{matrix} \sum_{k}a_{i} & = & nk \\ \sum_{k}b_{i} & = & nk\\ \sum_{k}c_{i} & = &nk \\ \sum_{k}d_{i} & = & nk \end{matrix} $$


$$ \begin{matrix} a_{i} +b_{i} & = & 2n, & \forall i \\ c_{i} +d_{i} & = & 2n, & \forall i \\ \end{matrix} $$

Find a lower bound on $\sum_{k}b_{i}d_{i}$ in terms of $n$ and $k$.

My attempt so far:

$$ \sum_{k}b_{i}d_{i} = \sum_{k}(2n-a_{i})(2n-c_{i})=4n^{2}k-2n\sum_{k}a_{i}-2n\sum_{k}c_{i} +\sum_{k}a_{i}c_{i} \\ = \sum_{k}a_{i}c_{i} $$

as $\sum_{k}a_{i}=\sum_{k}c_{i} = nk$

Similarily, we can show $\sum_{k}a_{i}d_{i} = \sum_{k}b_{i}c_{i} $.

Now let $\alpha = \sum_{k}b_{i}d_{i}$ and $\beta = \sum_{k}b_{i}c_{i}$, then $\alpha + \beta = 2n^{2}k$. I am not sure how to proceed from here.

I can't seem to fit AM-GM or Cauchy-Schwarz here. I have a feeling that I need to use rearrangement inequality, but unsuccessful so far.

  • $\begingroup$ The summation indices should be $i$ instead of $k$, it seems. $\endgroup$ – eccheng Mar 4 at 1:13
  • 1
    $\begingroup$ Also, $\sum_i b_id_i$ can be zero when $k$ is even: let $a_i$ and $d_i$ equal $0$ for $i \leq k/2$ and $2n$ for $i > k/2$, while $b_i$ and $c_i$ equal $2n$ for $i \leq k/2$ and $0$ for $i > k/2$. $\endgroup$ – eccheng Mar 4 at 1:20
  • $\begingroup$ That's correct. You can post it as answer. $\endgroup$ – zimbra314 Mar 4 at 4:42

Since $a_i = 2n - b_i$ and $c_i = 2n - d_i$ for all $i$, the equalities $\sum_i a_i = nk$ and $\sum_i c_i = nk$ follow from $\sum_i b_i = \sum_i d_i = nk$. Thus we can ignore $a_i$ and $c_i$ entirely, and the problem reduces to finding the best lower bound for $\sum_i b_id_i$ where $b_1, \dotsc, b_k$ and $d_1, \dotsc, d_k$ are sequences satisfying $$ \sum_i b_i = \sum_i d_i = nk \,,\quad 0 \leq b_i,d_i \leq 2n \quad \forall i \,. $$ Let us first suppose $k$ is even: we can set $$ b_i = \begin{cases} 2n &: i \leq k/2 \\ 0 &: i > k/2 \end{cases} \,,\quad d_i = \begin{cases} 0 &: i \leq k/2 \\ 2n &: i > k/2 \end{cases} \,, $$ giving $\sum_i b_i d_i = 0$, and this shows that $0$ is the best possible lower bound. Now consider the case where $k$ is odd. We can set $$ b_i = \begin{cases} 2n &: i \leq (k+1)/2 \\ n &: i = (k+1)/2 \\ 0 &: i > (k+1)/2 \end{cases} \,,\quad d_i = \begin{cases} 0 &: i \leq (k+1)/2 \\ n &: i = (k+1)/2 \\ 2n &: i > (k+1)/2 \end{cases} \,, $$ to get $\sum_i b_i d_i = n^2$, and we claim that this $n^2$ is the best possible lower bound on $\sum_i b_id_i$. Indeed, let $b'_1, \dotsc, b'_k, d'_1, \dotsc, d'_k$ be such that $\sum_i b'_id'_i$ is minimized (such choices must exist because the set of possible $(b_1, \dotsc, b_k, d_1, \dotsc, d_k)$ is compact), and re-index the terms so that $b'_1 \geq \dotsb \geq b'_k$. By the rearrangement inequality we must have $d'_1 \leq \dotsb \leq d'_k$, since otherwise $\sum_i b'_i d'_i$ would not be minimized. Note that if we decrease $b'_1$ to $0$ and redistribute the value of $b'_1$ between the other $b'_i$ (while maintaining $b'_1 \geq \dotsb \geq b'_k$), we will not increase the value of $\sum_i b'_i d'_i$; thus we can assume $b'_1 = 0$ while still knowing that $\sum_i b'_i d'_i$ is minimized. In the same way, we can ensure $d'_1 = 2n$, $b'_k = 2n$, and $d'_k = 0$. Continuing this process with $b'_2, d'_2, b'_{k-1}, d'_{k-1}$, and then with $b'_3, d'_3, b'_{k-2}, d'_{k-2}$, and so on, we can make the $b'_1, \dotsc, b'_k, d'_1, \dotsc, d'_k$ identical to the $b_1, \dotsc, b_k, d_1, \dotsc, d_k$ we defined explicitly above, while preserving the minimality of $\sum_i b'_i d'_i$. It follows that $\sum_i b_id_i = n^2$ is the minimum possible value for $\sum_i b_i d_i$, as desired.


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.