Conditional distribution

[nuuskur]

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 2ⁿ - 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 2ⁿ - 1 people at the party.

 

[haruspex]

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?

 

[nuuskur]

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:
$$C_1 = \{x_1\}\\C_2 = \{x_1, x_2\}\\C_3 = \{x_1, x_2, x_3\}$$

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 x_i that is in every set of presents, but then we can have another person at the party who receives the gift x_i, therefore if the maximum amount of people are attending, the smallest set of gifts contains one present.

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

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

Now I see an easier way - we must consider the subsets that contain x_i - that leaves n-1 types to choose from. The number of subsets of n-1 types is 2^n-1