Optimization over combinations of $n$ balls over $k$ bins.

Consider $$n$$ balls and $$k$$ bins, $$n \geq k$$. We put all balls in the bins. There can be empty bins, as well as more than one ball in each bin. Let $$c_i$$ the number of balls inside the $$i$$-th bin.

I'm trying to find the maximum w.r.t. $$c_1, \ldots, c_k$$ of the following quantity:

$$f(k,n) = \sum_{i=1}^k c_i(n-c_i).$$

It can be useful to notice that:

$$f(k,n) = \sum_{i=1}^k c_in- \sum_{i=1}^k c_i^2 = n^2 - \sum_{i=1}^k c_i^2,$$

since $$\sum_{i=1}^k c_i = n.$$

• Considering the special case where $n=ak$ for some positive integer $a$, it seems spreading the balls out evenly among the bins minimizes $\sum_i c_i^2$. May 3 '21 at 16:01
• @angryavian thanks for this. I also thought about this. But I need the upper bound of the function when only integers are allowed. May 3 '21 at 16:04
• @the_candyman are you looking for a closed form formula? I can't think of a nice one. May 3 '21 at 16:11
• @kyary yes, I'd like to have something like $f(k,n) \leq F(k,n).$ May 3 '21 at 16:18

There are a variety of techniques to show that $$\sum_{i=1}^k c_i^2$$ is minimized when all the $$c_i$$ are as close together as possible.

Not sure about what degree of rigor you want, but one easy method would be Lagrange multipliers.

A more rigorous way would be to first consider the k=2 case.

For the k = 2 case, say there are $$a$$ balls in the first bin and $$n-a$$ balls in the second bin.

By using cosine law on a degenerate triangle (lol), we get $$n^{2} = a^2 + (n-a)^{2} + 2a(n-a)$$

which gives us $$a^{2} + (n-a)^{2} = n^2 - 2a(n-a)$$. From grade 10 math, we see that $$a(n-a)$$ is maximized when $$(n-a)$$ and $$a$$ are as close together as possible, which would minimize the right hand side of the equation.

Thus, we see that this minimization condition works for the k=2 case.

For higher k, simply assume that the minimization condition does not hold (i.e. there exist two bins with one bin having at least 2 more balls than the other bin) and apply the k=2 case to these 2 bins to get a contradiction. (i.e. the minimum has not been achieved)

Now, as for an upper bound for your answer, I can't think of a closed form formula, but a hard bound would be

$$n^2 - \sum_{i=1}^{n mod k} (floor(n/k) + 1)^{2} - \sum_{i=1}^{k - (n mod k)} (floor(n/k))^{2}$$

A non-hard upper bound that looks nicer is $$n^2 - k (floor(n/k)+1)^{2}$$

The minimum of $$\sum c_i^2$$ (which maximizes $$f(k,n)$$) ls achieved when all bins have approximately the same number, i.e. $$\max|c_i-c_j|\le 1$$.