• Support PF! Buy your school textbooks, materials and every day products Here!

Conditional distribution

  • Thread starter nuuskur
  • Start date
  • #1
525
345

Homework Statement


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?

Homework Equations




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.
 

Answers and Replies

  • #2
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,721
5,028
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?
 
  • #3
525
345
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:

Related Threads on Conditional distribution

  • Last Post
Replies
1
Views
2K
Replies
2
Views
4K
  • Last Post
Replies
6
Views
780
  • Last Post
Replies
3
Views
981
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
511
Top