0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Arnaud D. Nov 7 '18 at 12:50
  • $\begingroup$ If no two persons can have the same number, how can more than one person have $0$? $\endgroup$ – Jens Nov 7 '18 at 17:09
2
$\begingroup$

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:

enter image description here

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

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