4
$\begingroup$

Suppose ther are B boys and G girls in a classroom.Teacher wants to distribute candies among B boys and G girls such that:

1.Each student gets atleast one candy and atmost N candies.
2.sum of candies given to all boys equals sum of candies given to all girls.

find the number of different ways to do it.
Note:Two ways are considered different if there exists a student that received different number of candies in these two candies' distributions.

Example: if B=1 G=2 N=3 there are 3 ways, they are: (2, 1, 1), (3, 1, 2), (3, 2, 1).
if B=2 G=2 N=2 there are 6 ways, they are: (1, 1, 1, 1), (1, 2, 1, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 2, 2, 2).

How to approach this problem?

$\endgroup$
  • $\begingroup$ what is the total number of candies? $\endgroup$ – Dheeraj Kumar Dec 20 '14 at 11:23
  • $\begingroup$ Assume Candies are infinite... $\endgroup$ – savvi singh Dec 20 '14 at 11:24
  • 2
    $\begingroup$ There need not be more than $N(B+G)$ candies or in fact $2N\min(B,G)$ candies $\endgroup$ – Henry Dec 20 '14 at 11:32
  • $\begingroup$ @Henry: yes you are right about that $\endgroup$ – savvi singh Dec 20 '14 at 11:35
  • 1
    $\begingroup$ Due to the symmetry of the problem, you may as well assume that $B \leq G$. $\endgroup$ – Gabe Cunningham Dec 20 '14 at 11:43
1
$\begingroup$

With the function $c(m,x,t)$ counting the number of ways of distributing $m$ candies among $x$ people so nobody received more than $t$ (but they could receive zero), the answer would be $$\sum_{m=\max(B,G)}^{N\min(B,G)}\; c(m-B,B,N-1)c(m-G,G,N-1)$$

Added: To calculate $c(m,x,t)$, note that for all $t$ you start with $c(0,0,t)=1$ and $c(m,0,t)=0$ for $m \gt 0$, and then for $x\gt 0$ you can use:

$$c(m,x,t)=\sum_{j=0}^{\min(m,t)} c(m-j,x-1,t).$$

E.g. if $t=1$ then you get a table for $c(m,x,t)$ starting

x  m:0 1 2 3  
-  ---------
0    1 0 0 0
1    1 1 0 0
2    1 2 1 0
3    1 3 3 1

while if $t=2$ then you get a table for $c(m,x,t)$ starting

x  m:0 1 2 3  
-  ---------
0    1 0 0 0
1    1 1 1 0
2    1 2 3 2
3    1 3 6 7

Considering your example of $B=1$, $G=2$, $N=3$ we get $$c(2-1,1,3-1)c(2-2,2,3-1)+c(3-1,1,3-1)c(3-2,2,3-1)$$ $$=c(1,1,2)c(0,2,2)+c(2,1,2)c(1,2,2)$$ $$=1\times 1 + 1\times 2 = 3$$

while considering your example of $B=2$, $G=2$, $N=2$ we get $$c(2-2,2,2-1)c(2-2,2,2-1)+c(3-2,2,2-1)c(3-2,2,2-1)+c(4-2,2,2-1)c(4-2,2,2-1)$$ $$=c(0,2,1)c(0,2,1)+c(1,2,1)c(1,2,1)+c(2,2,1)c(2,2,1)$$ $$=1\times 1 + 2\times 2 + 1\times 1 = 6$$

so this approach reproduces your expected results.

$\endgroup$
  • $\begingroup$ how to check if sum of candies given to boys is equal to sum of candies given to girls!!also each student receives atleast one candy!! $\endgroup$ – savvi singh Dec 20 '14 at 12:24
  • $\begingroup$ @savvi singh: the number of ways of distributing $m-B$ balls among $B$ boys so each gets no more than $N-1$ is the same as the the number of ways of distributing $m$ balls among $B$ boys so each gets no more than $N$ and each gets at least one. Similarly the number of ways of distributing $m-G$ balls among $G$ girls so each gets no more than $N-1$ is the same as the the number of ways of distributing $m$ balls among $G$ girls so each gets no more than $N$ and each gets at least one. So this meets both your points. Calculating $c(m,x,t)$ is the hard part. $\endgroup$ – Henry Dec 20 '14 at 16:42
0
$\begingroup$

Each boy should get G number of candies and each girl should get B number of candies. This would ensure that sum of the candies received by boys and girls is equal.

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