# Conditional distribution

## 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?

## 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.

haruspex
Homework Helper
Gold Member
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?

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 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 $\binom{n-1}{2}$ possibilities to combine the sets of gifts that contain xi
.
.
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 xi - that leaves n-1 types to choose from. The number of subsets of n-1 types is 2n-1

Last edited: