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.
The Answer to the Question
is below this banner.
Here's the Solution to this Question
Proposition. (The Pigeonhole Principle, simple version.)
If pigeons stay in holes then there is a hole with at least two pigeons.
We shall use the pigeonhole principle:
Consider the 5 pairs of numbers
In each case, the sum of the two numbers is
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.