0
$\begingroup$

A grandmother is cleaning out her garage and finds 6 items that she no longer wants to store. She has two charities that she likes to donate to, so she is going to put the 6 items into two boxes. She wants to give at least one item to each charity. She does not care which charity gets which items, so the boxes are not labeled.

How many different ways are there for her to place the 6 items into 2 unlabeled boxes?

For example {{$1,2,3,4$},{$5,6$}} is one way and {{$1,2,4,5$},{$3,6$}} is another.

But {{$1,2,3,4,6$},{$5$}} is the same as {{$5$},{$1,2,3,4,6$}}? The choices are 31 11 36 30 12 15

$\endgroup$
2
$\begingroup$

In the first box you have to put either 1, 2, 3, 4 or 5 items. Remaining items should go into the second box.

Number of ways to pick elements for the first box is therefore:

$$\binom{6}{1}+\binom{6}{2}+\binom{6}{3}+\binom{6}{4}+\binom{6}{5}=2^6-\binom{6}{0}-\binom{6}{6}=62\tag{1}$$

But boxes are unlabeled: if you denote the set in the first box with $A$ and in the second box with $B$, arrangements (A,B) and (B,A) are equivalent. In other words, each distinct combination is counted twice in (1). So the result is (1) divided by 2, which is 31.

$\endgroup$
  • $\begingroup$ @OsamaNatouf Your choices are 31, 11, 36, 30, 12, 15 and my answer is 31. So what is wrong with my answer? $\endgroup$ – Oldboy Feb 18 at 19:36
  • $\begingroup$ I apologize for that. $\endgroup$ – Osama Natouf Feb 18 at 19:55
  • $\begingroup$ @No hard feelings :) $\endgroup$ – Oldboy Feb 18 at 19:57
2
$\begingroup$

One box will contain item $6$. Together with $6$ there can be any subset of $[5]:=\{1,2,3,4,5\}$ other than $[5]$ itself. There are $2^5-1=31$ such subsets; and this is the answer to your question.

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