1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Conditional distribution

  1. Jan 27, 2015 #1
    1. The problem statement, all variables and given/known data
    Santa has n types of presents. Every child can receive at most one present of each type and:
    a) every child has to get a present AND cannot receive the same set of presents as any other child.
    b) for every 2 children, there must be a present that both of the children get
    How many children can attend the Christmas party at most?

    2. Relevant equations


    3. The attempt at a solution
    Assuming my interpretation is correct:
    Every child getting at most one of each present type - is this a fancy way of saying injection?
    All sets of presents have to be different. There are 2n - 1 different sets of presents (we cannot count the empty set since every child has to have a present - we are not concerned if the children do not receive the same number of presents i.e the cardinalities need not be equal).

    Per every 2 children, they must have a common present - this is the troublesome bit. What does it mean, exactly?
    I am sure it doesn't mean that ALL of the chosen subsets need to have a common element.

    This seems to be the attendance limiter - otherwise I can have 2n - 1 people at the party.
     
  2. jcsd
  3. Jan 27, 2015 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Suppose you allocate some (proper) subset of the types to a child. That rules out some other subsets for what can be allocated in future. Having allocated subsets to r children, can you find a lower bound for the number of subsets that have been ruled out?
     
  4. Jan 28, 2015 #3
    If I simplify - assume that there is a child that receives only one present, then by the condition:
    Per every 2 child, they must have a common present.

    This means that everybody has to have the same gift as the child with one gift.
    looks something:
    [tex]C_1 = \{x_1\}\\C_2 = \{x_1, x_2\}\\C_3 = \{x_1, x_2, x_3\}[/tex]

    I propose that:
    if the maximum amount of people are attending, then there is one person who receives one present
    there can be Only one person who receives one present.

    If there are 2 people who receive one present, then they do not have a common present, because no two sets can be identical and that also violates the next condition.

    IF the smallest set of gifts has 2 presents, then there has to be a present xi that is in every set of presents, but then we can have another person at the party who receives the gift xi, therefore if the maximum amount of people are attending, the smallest set of gifts contains one present.

    For 2 gifts, if xi is present, there are also n-1 possibilities for the second gift.
    For 3 gifts, if xi is present, there are [itex]\binom{n-1}{2}[/itex] possibilities to combine the sets of gifts that contain xi
    .
    .
    Careless mistake - I had written [itex]\sum_{k=0}^n \binom{n-1}{k}[/itex], but after k = n we get error :D

    There would be [itex]\sum_{k=0}^{n-1}\binom{n-1}{k} = 2^{n-1}[/itex] possible ways - the maximum amount of people attending.

    Now I see an easier way - we must consider the subsets that contain xi - that leaves n-1 types to choose from. The number of subsets of n-1 types is 2n-1
     
    Last edited: Jan 28, 2015
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted