written 7.7 years ago by | modified 2.6 years ago by |
Mumbai University > Computer Engineering > Sem 3 > Discrete Structures
Marks: 8 Marks
Year: May 2015
written 7.7 years ago by | modified 2.6 years ago by |
Mumbai University > Computer Engineering > Sem 3 > Discrete Structures
Marks: 8 Marks
Year: May 2015
written 7.7 years ago by |
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.
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}$