Problem on Pigeon-Hole Principle

Question

A college has 39 departments, and a total of 261 faculty members in those departments. Prove that there are three departments in this college that have a total of at least 21 faculty members.

This is a extra question in the fourth edition of 'Walk through Combinatorics', I can't think of how I should apply PHP here. I am self studying combinatorics through this book, it'd be helpful if I could get any hint on how to proceed.

Answer 1

Consider the list of all possible trios of departments and their corresponding totals of number of faculty members.

If we add up all of these totals corresponding to each of the possible trios of departments, how many times did the number of faculty members of the first department contribute to the sum? The second department's number of faculty members contribute to the sum? What should the overall total of this sum of all possible trios' totals equal?

Supposing that every trio's total was actually $20$ or less, does that cause a problem?

$\binom{38}{2}\cdot 261 > 20\cdot \binom{39}{3}$

Answer 2

As the questions involves three departments, let us group the 39 departments as units of 3 departments each. Thus, we get 13 units with 3 departments each.

Now, applying Pigeon-Hole Principle, at least one unit exists which has 21 faculty members in it. Hence proved.

Note that we are asked that 21 faculty members are in 3 departments in total and not in 3 departments with 21 member each.