pigeonhole principle problem solving

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.

Cloud Advisory Services | Security Advisory Services | Data Science Advisory and Research

Specializing in high volume web and cloud application architecture, Anuj Varma’s customer base includes Fortune 100 companies (dell.com, British Petroleum, Schlumberger).

All content on this site is original and owned by AdverSite Web Holdings, Inc. – the parent company of anujvarma.com. No part of it may be reproduced without EXPLICIT consent from the owner of the content.

Anuj Varma – who has written posts on Anuj Varma, Technology Architect.


Leave a Reply

Your email address will not be published. Required fields are marked *