|
|
|
Prove that if any set of nine distinct integers has sum greater than 200, then there is a subset of four of the integers whose sum is greater than 100.
Source: unknown
Suppose S is a set of nine distinct integers whose sum is greater than 200 with no 4-element subset whose sum is greater than 100. Let A be the set consisting of the four largest elements of S. The smallest element of A can be no bigger than 23, because 24+25+26+27>100. So the five smallest elements of S range in size from 1 to 22. The sum of the five smallest elements of S could not be bigger than 18+19+20+21+22=100, and the sum of the four largest elements are not bigger than 100, so the sum of the nine elements of S is not greater than 200, a contradiction.
(none)
(none)
(none)
The webmaster and author of this Math Help site is Graeme McRae.