Suppose 82 students are enrolled in a college – offering only 4 courses. Suppose that each course has 3 sections – and a student can choose any one of three sections. Show that at least TWO students have to share a section!
The solution is simple if we use the Pigeon Hole Principle. If you have 10 pigeons and only 9 pigeon holes, then two pigeons must share a hole. Sounds obvious – but it has some cool implications.
4 courses with 3 sections each – means that the total possible combinations that a student can make for a section are (one of 3 sections) x (one of 3 sections) x (one of 3 sections) x (one of 3 sections).
That’s 3 ^ 4 = 81 possible picks. So – each student has 81 possible picks – even if 81 students pick distinct sections – there will still be a section left over.
Thus, two students MUST share a section.