Results 1 to 13 of 13

Math Help - Ice-cream and cookie combinatorix

  1. #1
    Junior Member
    Joined
    Apr 2006
    Posts
    26

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by dnlstffrd View Post
    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 \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 \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 \left( {\emptyset ,\emptyset } \right) because of the given.

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

    Can you finish?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2006
    Posts
    26
    What cases can we not have besides 1 person having to have a cookie and an ice cream cone?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by dnlstffrd View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2006
    Posts
    26
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1
    You must eliminate all pairs \left( {A,B} \right) where either A = \emptyset, B = \emptyset, or both. There are no others to worry with.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Apr 2006
    Posts
    26
    so then it would just be 2^8*2^8*2^8 - 3 or 16777213 right?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by dnlstffrd View Post
    so then it would just be 2^8*2^8*2^8 - 3 or 16777213 right?
    That is a gross overcount. Say E = \{ 1,2,3,...,7,8\} is the set of the eight people.
    The number of subsets of E is 2^8 .
    There are 2^8 pairs of the form \left\{ {\left( {A,\emptyset } \right):A \subseteq E} \right\}.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Apr 2006
    Posts
    26
    Oh, I get it now. Thanks for the help! Sorry, I'm really horrible at sets.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Sep 2007
    Posts
    75
    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'.

    Now to acknowledge the cookies:
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by Obsidantion View Post
    . 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 \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 \left( {\left\{ {1,2,3,4} \right\},\left\{ {5,6,7,8} \right\}} \right) because there is none gets both. Therefore of the 2^{16} possible pairs we must exclude any pair that has this property: \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 \sum\limits_{k = 0}^8 {_8 C_k \left( {2^{8 - k} } \right)} .
    So the total we want is 2^{16}  - \left[ {\sum\limits_{k = 0}^8 {_8 C_k \left( {2^{8 - k} } \right)} } \right].
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Obsidantion View Post
    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 4^8-3^8 = 58975.

    Edit This agrees with Plato's calculation, since \sum\limits_{k = 0}^8 {_8 C_k \left( {2^{8 - k} } \right)} = (1+2)^8 = 3^8.
    Last edited by Opalg; September 20th 2007 at 01:36 AM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Sep 2007
    Posts
    75
    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:

    Quote Originally Posted by Opalg View Post
    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 4^8-3^8 = 58975.

    (Very good job)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Ice Cream Problem
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: October 13th 2011, 02:01 PM
  2. How Many Choices of Ice Cream?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 22nd 2010, 02:56 PM
  3. Cookie Question!!
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: April 29th 2008, 10:51 AM
  4. Change combinatorix
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 28th 2007, 02:44 PM
  5. Ice Cream
    Posted in the Statistics Forum
    Replies: 2
    Last Post: September 22nd 2006, 03:14 AM

Search Tags


/mathhelpforum @mathhelpforum