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