Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 8 Marks

Year: Dec 2014

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 pairs : (1,6)(2,5)(3,4)
hole #1 : for numbers 1 2 3 
hole #2 : for numbers 4 5 6 
111  1
---  --- 
#1   #2
If you pick 4 numbers you are guaranteed to hit a solution