0
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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$. $\endgroup$
    – angryavian
    May 3 '21 at 16:01
  • $\begingroup$ @angryavian thanks for this. I also thought about this. But I need the upper bound of the function when only integers are allowed. $\endgroup$ May 3 '21 at 16:04
  • $\begingroup$ @the_candyman are you looking for a closed form formula? I can't think of a nice one. $\endgroup$
    – kyary
    May 3 '21 at 16:11
  • $\begingroup$ @kyary yes, I'd like to have something like $f(k,n) \leq F(k,n).$ $\endgroup$ May 3 '21 at 16:18
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.