3
$\begingroup$

It is from a programming contest but I feel it pertains more to the mathematics realm ( I once asked it in stackoverflow but they closed the problem saying I should go here )

The problem goes like this:

You are a teacher of a kindergarten class. There are $n$ students in your class and now you want to buy candies for them as year end prizes.

The candy you want to buy is called "colorful", and it has $5$ colors: red, blue, green, yellow, and purple.

There are just one rule: each student can only have one color of candies in their hands. Different students can have different colors though.

When you go to the candy store, you are surprised by the fact that all candy bags from "colorful" are opaque. What you know is, each bag holds $20$ candies. For example, it can contain all $5$ colors, or just one color. ( all other combinations are also possible) You can not tell how many candies of each color in any bag.

Here comes the challenge. If you have $n$ students and you want to hand them $m$ candies each student, what is the minimum number of bags of "colorful" candy you should buy, so that the rule (each student have 1 color) is never broken?

Some examples:

$n=1$, $m=5$. You need $2$ bags. Because in the worst case, the first bag have $5$ colors and $4$ candies each. You still need $1$ candy for any color to meet $5$.

$\endgroup$
2
$\begingroup$

Let's generalise this, with $c$ colours and $b$ bags with $a$ candies in each bag.

You can have up to $c(m-1)$ candies in incomplete sets plus $(n-1)m$ in complete sets and still fail, but you will succeed with one more candy, so if your total number of candies $ab \ge (n-1)m + c(m-1)+1$ then you must have at least $n$ handfuls of $m$ of a single colour. So $$b \ge \dfrac{nm+cm-m-c+1}{a}$$ and the minimum integer involves rounding up $$\left\lceil \dfrac{nm+cm-m-c+1}{a}\right\rceil.$$

In your example $a=20, c=5, n=1, m=5$ so you need $\left\lceil \frac{5+25-5-5+1}{20}\right\rceil=\left\lceil \frac{21}{20}\right\rceil=2$ bags to be certain of success.

$\endgroup$
  • $\begingroup$ I agree with your inequalities. but how do you make sure the lower bound of this inequality is reachable with random distribution of candies in any bag? $\endgroup$ – user694345 Dec 20 '14 at 22:42
  • $\begingroup$ Your example was not random, but a worst case. My $(n-1)m + c(m-1)$ is a general worst case of the most candies you can have and still fail as $1$ more will guarantee you $n$ complete sets of $m$ candies $\endgroup$ – Henry Dec 20 '14 at 22:49

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.