**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
```