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

69 Views Asked by At

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

2

There are 2 best solutions below

0
On BEST ANSWER

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

0
On

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