State and explain Pigeonhole principle, extended Pigeonhole principle. How many numbers must be selected from the set {1,2,3,4,5,6} to guarantee that at least one pair of these numbers add up to 7?

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 …