Need help To Understand Pigeonhole Principle

Mathematics for Computing
User avatar
Neo
Site Admin
Site Admin
Posts: 2642
Joined: Wed Jul 15, 2009 2:07 am
Location: Colombo

Re: Need help To Understand Pigeonhole Principle

Post by Neo » Mon Jul 04, 2011 1:53 pm

For the theorems explained in Herath's post, you need to know about Floor and Ceiling of numbers. I have added a little post on that. What are ceiling and floor in mathematics?

Generalizations of the pigeonhole principle
A generalized version of this principle states that, if N discrete objects are to be allocated to k containers, then at least one container must hold no fewer than ⌈N / k⌉ objects. Similarly, at least one container must hold no more than ⌊N/k⌋ objects.

First question.
k = 4, We need to find N.
⌈N / 4⌉ = 4
N should be minimum 13 to be ⌈13 / 4⌉ = ⌈3.25⌉ = 4

To verify, ⌈12 / 4⌉ = ⌈3⌉ = 3, So 12 is not going to work.
Second part,
There are 7 days in a week. Then we have 7 pigeonholes. So the answer should be 29.
I'll give a little explanation.

k = 7, We need to find N.
⌈N / 7⌉ = 5
N should be minimum 29 to be ⌈29 / 7⌉ = ⌈4.14⌉ = 5

To verify, ⌈28 / 7⌉ = ⌈4⌉ = 4, So 28 is not going to work.
Third part,
There are 12 months in a year. So we have 12 pigeonholes. In order to have at least 2 students born in the same month we should have 13 students in the class.
k = 12, We need to find N.
⌈N / 12⌉ = 2
N should be minimum 13 to be ⌈13 / 12⌉ = ⌈1.083⌉ = 2

To verify, ⌈12 / 12⌉ = ⌈1⌉ = 1, So 12 is not going to work.
Post Reply

Return to “Mathematics”