A course has seven elective topics and students must complet

A course has seven elective topics, and students must complete exactly three of them in order to pass the course. If 200 students passed the course, show that at least 6 of the students must have completed the same electives as each other? [Hint: Use the Pigeonhole Principle.

Solution

Let us first count the number of topic choices. There are 7 course and a student must choose 3 among them. Therefore there are

7C3 = 35

such choices.

Now there are 200 students. Suppose that there are at most 5 students that have completed the same electives as each other. We have

5×35=175.

But 175<200 and therefore at least 6 students have completed the same electives.