Question

Explain pigeon hole principle. Using this principle show that in any group of 36 people, we can always find 6 people who were born on the same day of week.

Answer 1

There are 7 days in a week. Think of each of these days as a "Pigeon Hole." The Pigeons are the people. So, we have 36 pigeons that need to fit into 7 pigeon holes.

Generally, if n pigeons are to be allocated to m pigeon holes, then at least one hole must hold no fewer than \(\lceil n/m \rceil\) objects, where \(\lceil x\rceil \)is the ceiling function, denoting the smallest integer larger than or equal to x. Here m=36 and m = 7, so \(\lceil 36/7 \rceil= 6\) .

More concretely:

We can put all pigeons into a single hole (indicating that 36 people were all born on that day), so definitely we have more than 6 pigeons (people) born on that day. Note that 6 of the holes are empty.

We can put all pigeons into 2 holes (meaning that all 36 people were born in 1 of 2 days). Of all possible combinations of 36 pigeons into 2 holes, the maximum can never be less than 18 pigeons, where we have an equal number in each hole. So again, we hae more than 6 pigeons in single hole, however we arrange them.

For arrangements of pigeons into 3 holes, them maximum can never be less than 36/3 = 12, so again we have more than 6 pigeons per hole in every possible arrangement.

For 4 holes, the maximum number of pigeons per hole can never be less than 36/4 = 9, which is greater than 6.

For 5 holes, the maximum number of pigeons per hole can never be less than \( \lceil{36/5\rceil} \)= 8, which is greater than 6. We use the ceiling function because we can not have a fraction of a pigeon.

For 6 holes, the maximum number of pigeons per hole can never be less than \( 36/6= 6\), which is greater than or equal to 6.

For 7 holes, the maximum number of pigeons per hole can never be less than \( \lceil{36/7\rceil} \)= 6,, which is greater than or equal to 6.

Therefore, we can always find 6 people who were born on the same day of week..