Question: Suppose there're 100 people in 15 committees of 20 people each, and that each person is on exactly 3 committees. Show that there exist 2 committees with overlap >= 3.
I know there's a solution using expected number of overlaps of any pair of committee. I want to know how to solve this problem (and problems of this type) in a purely combinatorial way (possibly using Pigeonhole Principle.)
We can think about it like this:
If we have $300$ people and $15$ committees, each will have $20$ with each person in only one committee.
If one person can serve in two committees, then we would need $\frac{300}{2} = 150$ people.
And so if one person can serve in three committees, we would need $\frac{300}{3} = 100$ people.
This makes sense as we would need all $\frac{300}{15} = 20$ people if each can serve in all $15$ committees.