1. ## Ice-cream and cookie combinatorix

Eight people are in a room. One or more of them get an ice-cream cone. One or more of them get a chocolate-chip cookie. In how many different ways can this happen, given that at least one person gets both an ice-cream cone and a chocolate-chip cookie?

2. Originally Posted by dnlstffrd
Eight people are in a room. One or more of them get an ice-cream cone. One or more of them get a chocolate-chip cookie. In how many different ways can this happen, given that at least one person gets both an ice-cream cone and a chocolate-chip cookie?
This is an exercise in counting ordered pairs of subsets.
For example, the pair $\displaystyle \left( {\left\{ {1,2,3,4} \right\},\left\{ {2,4,6,8} \right\}} \right)$ represents the case where persons 1,2,3, & 4 get ice-cream cones while persons 2,4,6, & 8 each gets a chocolate-chip cookie.
If A is a non-empty subset of the eight, we cannot have the pairs $\displaystyle \left( {\emptyset ,A} \right)\mbox{ or }\left( {A,\emptyset } \right)$ because we are given “that at least one person gets both an ice-cream cone and a chocolate-chip cookie”. Likewise we cannot have the pair $\displaystyle \left( {\emptyset ,\emptyset } \right)$ because of the given.

There are $\displaystyle 2^8$ subsets of a set of eight. There are $\displaystyle 2^8 \times 2^8$ ordered pairs of those subsets. Now remove the cases we cannot have.

Can you finish?

3. What cases can we not have besides 1 person having to have a cookie and an ice cream cone?

4. Originally Posted by dnlstffrd
What cases can we not have besides 1 person having to have a cookie and an ice cream cone?
How in the world did you come to the conclusion that you should exclude that case? Did you read the given in the problem? Then did you try to follow the logic in the reply I gave above?

5. Whoops, I didn't mean that. I meant cases besides where no one gets either an ice cream cone or a cookie, or there are none of either.

6. You must eliminate all pairs $\displaystyle \left( {A,B} \right)$ where either $\displaystyle A = \emptyset$, $\displaystyle B = \emptyset$, or both. There are no others to worry with.

7. so then it would just be 2^8*2^8*2^8 - 3 or 16777213 right?

8. Originally Posted by dnlstffrd
so then it would just be 2^8*2^8*2^8 - 3 or 16777213 right?
That is a gross overcount. Say $\displaystyle E = \{ 1,2,3,...,7,8\}$ is the set of the eight people.
The number of subsets of E is $\displaystyle 2^8$.
There are $\displaystyle 2^8$ pairs of the form $\displaystyle \left\{ {\left( {A,\emptyset } \right):A \subseteq E} \right\}$.

9. Oh, I get it now. Thanks for the help! Sorry, I'm really horrible at sets.

10. I thought I'd step in to provide an alternative, more visual approach (for anyone who doesn't understand):

You have 8 people, one of which must have an ice-cream and a cookie:

That leaves 7 people to have any combination of ice-creams and cookies (as illustrated by the question marks).
If we start off simply by looking at the amount of combinations 1 person can have, with regard to ice-creams only, we get 2 combinations:

If we consider 2 people, each with the possibility of having either an ice-cream or not, we get 4 possible combinations:

This is because for every possible option that person number 2 has (2 options), there will be 2 options for person number 1 which means that there will be the 2 combinations of person number 1 when person number 2 has got an ice-cream and also, in addition, the same 2 combinations of person number 1 when person number 2 has not got an ice-cream. So we can conclude that every time we consider an extra person, the number of combinations doubles as there are two new sets of combinations (one with the additional person having an ice-cream and one without). This can be represented as 2 ^ 'Number of People'.

For every single possible combination of cookies, there will be a whole set of every combination of ice-creams between 7 people to account for (1 of the people isn’t counted because they only have one possible option, to have both an ice-cream and a cookie). This means that we need to multiply all the combinations of ice-creams by all the combinations of cookies (one total amount of combinations of ice-creams for each combination of cookies). These are the same because they both have binary values (have got or have not got) with the same amount of people involved, meaning that the answer is to square (2 ^ ‘Number of People’ or 7) which makes 16,384 combinations.

11. Originally Posted by Obsidantion
. These are the same because they both have binary values (have got or have not got) with the same amount of people involved, meaning that the answer is to square (2 ^ ‘Number of People’ or 7) which makes 16,384 combinations.
Frankly, I do not know if this should be continued. But as the other was an over-count, this is an undercount. Again, we are counting ordered pairs of subsets of a set of eight. The pair $\displaystyle \left( {\left\{ {1,2,4,5} \right\},\left\{ {5,6,7,8} \right\}} \right)$ represents the way that persons 1,2,4, & 5 each gets an ice-cream cone and persons 5, 6, 7, & 8 each gets a cookie. Person 5 gets both. We cannot use the pair $\displaystyle \left( {\left\{ {1,2,3,4} \right\},\left\{ {5,6,7,8} \right\}} \right)$ because there is none gets both. Therefore of the $\displaystyle 2^{16}$ possible pairs we must exclude any pair that has this property: $\displaystyle \left( {A,B} \right):A \cap B = \emptyset$. That is, we can only count pairs of subsets that that have a non-empty intersection; we know that at least one person gets both a cone and a cookie.
The number of such pairs is $\displaystyle \sum\limits_{k = 0}^8 {_8 C_k \left( {2^{8 - k} } \right)}$.
So the total we want is $\displaystyle 2^{16} - \left[ {\sum\limits_{k = 0}^8 {_8 C_k \left( {2^{8 - k} } \right)} } \right]$.

12. Originally Posted by Obsidantion
For every single possible combination of cookies, there will be a whole set of every combination of ice-creams between 7 people to account for (1 of the people isn’t counted because they only have one possible option, to have both an ice-cream and a cookie). This means that we need to multiply all the combinations of ice-creams by all the combinations of cookies (one total amount of combinations of ice-creams for each combination of cookies). These are the same because they both have binary values (have got or have not got) with the same amount of people involved, meaning that the answer is to square (2 ^ ‘Number of People’ or 7) which makes 16,384 combinations.
I think we're still not quite there. The above analysis assumes that there is one designated person (out of the eight) who gets both an ice-cream and a cookie. There is no reason why it shouldn't be one of the other seven (but then we get into problems of double counting because there may be more than one person who gets both).

The simplest way to get an accurate count is to say that for each of the eight people there are four possibilities: ice-cream, cookie, both, or neither. That gives 4^8 combinations. But we must exclude all the cases where nobody gets both. There are 3^8 such combinations (because in that case there are only three possibilitites for each person: ice-cream, cookie, or neither). The answer to the problem is therefore $\displaystyle 4^8-3^8 = 58975$.

Edit This agrees with Plato's calculation, since $\displaystyle \sum\limits_{k = 0}^8 {_8 C_k \left( {2^{8 - k} } \right)} = (1+2)^8 = 3^8.$

13. Ops, I thought the designated ice-cream and cookie customer was a particular person of the 8, my mistake. These guys above are right.

I couldn't explain anything faster or more simply then this:

Originally Posted by Opalg
The simplest way to get an accurate count is to say that for each of the eight people there are four possibilities: ice-cream, cookie, both, or neither. That gives 4^8 combinations. But we must exclude all the cases where nobody gets both. There are 3^8 such combinations (because in that case there are only three possibilitites for each person: ice-cream, cookie, or neither). The answer to the problem is therefore $\displaystyle 4^8-3^8 = 58975$.

(Very good job)