3
$\begingroup$

Could you please tell me if my answer correct?

Here is the problem:

How many ways can 10 candy bars and 8 lollipops be given to five nameless, faceless, pitifully anonymous and altogether indistinct children so that every child gets at least one of each, but no child gets more than two lollipops?

Here is my answer:

First part of the problem: candy bars

As every indistinct children will receive at least one candy bar, the problem is equivalent to distribute five identical candy bars to five indistinct children. This problem is equivalent to answer the question how many integers partitions have the number 5?

We know that there are 7 partitions of 5:

5

4+1

3+2

3+1+1

2+2+1

2+1+1+1

and

1+1+1+1+1

Then the answer to the first part of the problem is 7.

Second part: lollipops

As every indistinct children will receive one or two lollipops, this problem is equivalent to answer the question how many integers partitions have the number 3, not allowing the partition {3}?

The only partitions are:

2+1 and

1+1+1

Thus the answer is 2.

Finally, by the multiplicative principle:

7*2 (7 ways to select the candy bars times 2 ways to select the lollipops).

Thus the final answer is 14.

$\endgroup$
6
  • 2
    $\begingroup$ Unfortunately not... I would consider the arrangement where one child gets 6 candybars and two lollipops different than an arrangement where one child gets 6 candybars and only one lollipop. Unfortunately multiplication principle wont work here how you like. Also, the partition $2+1$ wont work because that would refer to a child getting three lolipops which was not allowed. There will specifically be three children with two lolipops each and two children with one lolipop each. $\endgroup$
    – JMoravitz
    Jun 5 '17 at 2:34
  • $\begingroup$ @JMoravitz Thank you so much for your help! I did not notice that 2+1 lollilops would not work..... $\endgroup$
    – Beginner
    Jun 5 '17 at 2:38
  • $\begingroup$ @JMoravitz Then by the multiplicative principle the answer would be 7. Right? $\endgroup$
    – Beginner
    Jun 5 '17 at 2:40
  • $\begingroup$ Read my comment again. No. $\endgroup$
    – JMoravitz
    Jun 5 '17 at 2:41
  • $\begingroup$ @JMoravitz Thank you for fast help! I will read it again. I am so sorry... I am very slow... $\endgroup$
    – Beginner
    Jun 5 '17 at 2:43
3
$\begingroup$

Unfortunately, we approach directly by brute force. I do not see a more convenient approach. We break first into cases by candybar distribution, and then break down further based on lolipop distribution.

  • $5+0+0+0+0$

Either the person with six candybars does or does not get two lollipops: 2 options

  • $4+1+0+0+0$

Choose whether the person with 5 candybars does or does not get two lollipops and choose whether the person with 2 candybars does or does not get two lollipops. $4$ options

  • $3+2+0+0+0$

Similar to last case: $4$ options

  • $3+1+1+0+0$

Choose whether the person with 4 candybars does or does not get two lollipops. Then, choose whether one, both, or none of the persons with 2 candybars get two lollipops. Then, note that it is impossible for all three of them not to get two lollipops, so subtract one from the count to correct that: $2\cdot 3-1=5$ options

  • $2+2+1+0+0$

Similar to last case, choose for the person with 2 candybars, then choose how many people with 3 candybars for $5$ options.

  • $2+1+1+1+0$

Choose whether the person with 3 candybars does or does not get two lollipops. Then, choose whether the person with 1 candybar does or does not get two lollipops. $4$ options

  • $1+1+1+1+1$

Clearly only one option here.


We have then for a grand total $2+4+4+5+5+4+1=25$ options

$\endgroup$
1
  • $\begingroup$ Thank you so much! Fantastic answer! Very clear! One question: this type of problem can be solved with generating functions? I am trying to understand when generating functions can be used and when not. $\endgroup$
    – Beginner
    Jun 5 '17 at 3:42
2
$\begingroup$

It's easier to start with lollipops.

Step 1: We give each child a lollipop (since each child must have at least one lollipop). Now there are 3 lollipops remaining, but no child can have 3, we must have:

  • exactly 3 children with exactly 2 lollipops, and
  • 2 children with exactly 1 lollipop.

    Since the children are indistinct, there is no choice here.

Step 2: We give each child a candy bar. Now there are 5 candy bars remaining.

We can use the partition technique in the question, but (a) we need to account for giving no additional candy bars to students, and (b) we need to account for the 1-lollipop and 2-lollipop students separately.

Suppose we distribute $i \in \{0,\ldots,5\}$ of these 5 candy bars to the children with 2 lollipops.

  • Case $i=0$.

    • One lollipop children receive either: 0+5, 1+4, 2+3.
    • Two lollipop children receive: 0+0+0.

      So there are 3*1=3 possibilities when $i=0$.

  • Case $i=1$. [snip] There are 3 possibilities.

  • Case $i=2$. [snip] There are 4 possibilities.

  • Case $i=3$. [snip] There are 6 possibilities.

  • Case $i=4$. [snip] There are 4 possibilities.

  • Case $i=5$. [snip] There are 5 possibilities.

Summing these gives 25 possibilities.

This can be verified with the GAP code:

T:=Filtered(Tuples([1..10],2),P->P[2]<=2);;
C:=UnorderedTuples(T,5);;
F:=Filtered(C,P->Sum(P,p->p[1])=10 and Sum(P,p->p[2])=8);;
Size(F);
$\endgroup$
4
  • 1
    $\begingroup$ Amazing answer! Thank you so much! $\endgroup$
    – Beginner
    Jun 5 '17 at 3:45
  • $\begingroup$ One question: this type of problem can be solved with generating functions? I am trying to understand when generating functions can be used and when not. $\endgroup$
    – Beginner
    Jun 5 '17 at 3:51
  • $\begingroup$ @Beginner: I'm not sure if I can answer that. Sometimes they work like magic, and sometimes they're more of an obstacle, and I don't have a way to determine which problems they are effective on in general. $\endgroup$ Jun 5 '17 at 3:55
  • $\begingroup$ Thank you so much again! I really appreciate your comment on generating functions! $\endgroup$
    – Beginner
    Jun 5 '17 at 3:57

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.