Answer to Question #270150 in Discrete Mathematics for bholu

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

For natural numbers ${\displaystyle k}$  and ${\displaystyle m},$ if ${\displaystyle n=km+1}$ objects are distributed among ${\displaystyle m}$ sets, then the Pigeonhole Principle asserts that at least one of the sets will contain at least ${\displaystyle k+1}$  objects.

Let us consider the partition of the set $\{3,4,5,6,7,8,9,10,11,12\}$ ito 5 subset: $\{3,12\}$, $\{4,11\}$, $\{5,10\},$ $\{6,9\}$ and $\{7,8\}.$ The sum of elements in each subset is equal to 15. Taking into account that there are 5 subsets and we choose 6 elements by Pigeonhole Principle we get that at least one pair will be selected. Consequently, there must be two integer whose sum is fifteen.