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.

Specializing in high volume web and cloud application architecture, Anuj Varma’s customer base includes Fortune 100 companies (dell.com, British Petroleum, Schlumberger).
Anuj also offers a 1-day ‘technology for executives, crash course’ focused on emerging technologies.
For Anuj’s specialized one-on-one executive seminars, visit ANUJ.COM
All content on this site is original and owned by anujvarma.com.

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 *