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!

Solution

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.

Anuj holds professional certifications in Google Cloud, AWS as well as certifications in Docker and App Performance Tools such as New Relic. He specializes in Cloud Security, Data Encryption and Container Technologies.

Initial Consultation

Anuj Varma – who has written posts on Anuj Varma, Hands-On Technology Architect, Clean Air Activist.

 Twitter Linkedin