# Combinatorics: Distributing $n$ bananas to $k$ people

If I have $$n$$ bananas that are all looking the same and distribute them to $$k$$ people, how many bananas does the person with the most bananas have at least, if no two persons can have the same amount of bananas?

The $$k$$ people can also have no bananas $$n$$.

Lets make a case analysis:

• n > k: If there are $$8$$ bananas and $$3$$ persons, we distribute like that: $$1,2,5$$ -> max = $$5$$. Or if there are $$13$$ bananas and $$4$$ persons, we distribute like that: $$1,3,4,5$$ or $$1,3,4$$ -> max = $$5$$ or $$4$$. If there are $$10$$ bananas and $$2$$ persons, then we distribute: $$4,6$$ -> max = $$6$$. I can't find a formula that satisfies altogether.
• n < k: If there are $$2$$ bananas and $$5$$ persons, then the person with most bananas would have $$2$$, meaning $$n$$
• n = k: If there are $$5$$ bananas and $$5$$ persons, we distribute like that: $$2,3$$ (because no two persons can have the same amount of bananas). So the person with most bananas has $$\lfloor\frac{n}{2}+1\rfloor$$

So the premise is $$n \geq \frac{k\cdot(k-1)}{2}$$

• In your first case, you could also distribute the $8$ bananas as $1,3,4$, and the $13$ as $1,3,4,5$; you have the wrong maximum. In your second and third case, is it admissible for several persons to have $0$ bananas? – Arnaud D. Nov 7 '18 at 12:50
• If no two persons can have the same number, how can more than one person have $0$? – Jens Nov 7 '18 at 17:09

Let's call the minimum number of bananas needed for $$k$$ people as $$n_0 = \frac{k\cdot(k-1)}{2}$$
The minimum number of bananas that the person with the most bananas can have is then $$\text{Min} = \lceil{\frac{n-n_0}{k}}\rceil + k - 1$$
An example with $$k=4$$ (and hence $$n_0=6$$) and $$n$$ varying:
For $$n=n_0+1$$, we need to add a banana to someone. We cannot add it to anyone other than the person with the most bananas, otherwise we would have two people with the same number of bananas. For $$n=n_0+2$$ we can add the new banana to the person with the most bananas or the person with the next-most. We don't want to give the person with the most any more than absolutely necessary, so we give it to the one with the next-most. This continues until we have added a banana to all $$k$$ people. The pattern then starts over.