"Balancing" Sums

67 Views Asked by At

Given are $x_1,\ldots, x_n\in \{0,1,\ldots,n\}$, $y_1,\ldots, y_n\in \{0,1,\ldots,n\}$ with the property that

$$\sum_{i=1}^{n}{x_i}\leq B,$$ $$\sum_{i=1}^{n}{y_i}\leq B$$

Let's assume that $B$ is smaller than $n^2$. This obviously means that if there is one (or a couple) very large $x_i$, then the remaining ones have to be much smaller (therefore "balancing" sums).

Now I want to bound the following sum: $\sum_{\{i,j\}\in I}^{}{x_i\cdot y_j}$. The sum iterates over some $\{i,j\}$, but they are always at most $B$ many summands in this sum, in other words, $|I|\leq B$.

How can I bound this sum knowing everything above?