# Find minimum of sum of product of sequences

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}$$

and

$$\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.

• The summation indices should be $i$ instead of $k$, it seems. – eccheng Mar 4 at 1:13
• 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$. – eccheng Mar 4 at 1:20
• That's correct. You can post it as answer. – 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.