Answer to Question #270423 in Discrete Mathematics for Rajan

Question

State the Pigeonhole Principle. Prove that if six integers are selected from the set

[3,4,5,6,7,8,9,10,11,12] there must be two integer whose sum is fifteen.

Answer 1

Proposition. (The Pigeonhole Principle, simple version.)

If $n + 1$ pigeons stay in $n$ holes then there is a hole with at least two pigeons.

We shall use the pigeonhole principle:

Consider the 5 pairs of numbers $(3,12), (4,11), (5,10), (6,9), (7,8).$

In each case, the sum of the two numbers is $15.$

These pairs will serve as our "pigeon-holes". If we select 6 distinct integers (i.e., the "pigeons") from the integers 3 to 12, inclusive -- then by the pigeonhole principle, at least two of them must be in the same pair. Since the 6 integers chosen were distinct, we have found two that add up to 15.