prove the existence of the same classes

Question

I am a beginner in combinatorial mathematics, this is a combinatorial mathematics course assignment. With 31 students each taking at least 6 courses from a total of 10 courses, I need to prove the existence of two students who have taken at least 5 of the same courses.help

Answer 1

First let us reduce it to the case where each student is taking exactly six courses. Simply have any student who is taking more than six courses drop down to exactly six. We will show that there must be two students with at least five courses in common. If we include the dropped courses, the number of courses these students have in common cannot decrease; it will remain at least five.

Now, for each student consider the set of seven-course schedules obtainable by adding one course to their existing schedule. For each student, there are four possible seventh courses to add.

For any two students, if they can attain identical seven-course schedules, then their current schedules must already overlap in at least five classes.

Thus, it suffices to show that two of these seven-course schedules must be identical. Now we may use the pigeonhole principle. The total number of possible seven-course schedules from a set of ten, ${10\choose 7}$, are the holes. Each of the $31$ students has four possible seven-course schedules, which are the pigeons.

$$4 \cdot 31=124>120={10\choose 7}$$

Thus at least two students have a possible seven-course schedule in common, and thus already overlap in five courses.