Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 8 Marks

Year: May 2015

Pigeonhole principle:

If k is a positive integer and k+1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.

Proof: We will prove the pigeonhole using a proof by contraposition. Suppose that none of the k boxes contains more than one object. Then the total number of objects would be at most k. This is a contradiction, because there are at least k+1 objects.

Extended Pigeonhole Principle:

It states that if n pigeons are assigned to m pigeonholes (The number of pigeons is very large than the number of pigeonholes), then one of the pigeonholes must contain at least [(n-1)/m]+1 pigeons.

Proof: we can prove this by the method of contradiction. Assume that each pigeonhole does not contain more than [(n-1)/m] pigeons. Then, there will be at most

m[(n-1)/m]≤m(n-1)/m=n-1 pigeons in all. This is in contradiction to our assumptions. Hence, for given m pigeonholes, one of thses must contain at least [(n-1)/m]+1 pigeons.

Problem:

solution : By extended pigeon hole principle at least $\bigg[\bigg|\dfrac{n-1}{m}\bigg|\bigg]+1$ pigeons will occupy one pigeon hole.

Hence n =50, m=7

then 7 < 50

$\bigg[\bigg|\dfrac{50-1}{7}\bigg|\bigg]+1$ $=7+1 \\ = 8 \text{bicycles will be of same colour}$