Simple question of maximum value a part can have?

67 Views Asked by At

We have to partition n chocolates among m children. Children will be happy if max and min a child has got is less than 2. What is the max a child can get??

For n=6 m=3 ,the partition will be 2 2 2 Maximum a child can get is 2

For n=7 m=3 ,the partition will be 2 3 2 Maximum a child can get is 3

How to get maximum without knowing the partition?

1

There are 1 best solutions below

9
On BEST ANSWER

Start by giving each child $\left\lfloor\frac{n}m\right\rfloor$ pieces; if there are any left over, give $n-m\left\lfloor\frac{n}m\right\rfloor$ of the children one more piece each. This is the only way to keep the difference between the minimum and maximum less than $2$. The maximum will then be $\left\lceil\frac{n}m\right\rceil$.

If the floor and ceiling functions are unfamiliar, let $n=mq+r$, where $0\le r<m$. If $r=0$, each child gets $q$ chocolates. (Giving any child more than that forces you to give some child fewer than $q$, making the difference between maximum and minimum greater than $1$.) If $r>0$, give $r$ children one more chocolate each; the maximum will then be $q+1$ and the minimum $q$.