Track / Stage 4 / 23 of 340 #763 of 2444

Problem 763

AMC 12 late, AIME early

Combinatorics Difficulty 4.1 Multiple choice Olimpiadi di Matematica · Italy

From the set $\{1,2, \ldots, 100\}$ we choose 50 distinct numbers, whose sum is 3000. At minimum, how many even numbers have we chosen?

Pick one

Official solution

Solution:

The answer is (E). The sum of all positive odd numbers less than 100 is 2500. Therefore in every subset $X$ of $\{1, \ldots, 100\}$ whose elements sum to 3000, the contribution of the even numbers of $X$ to the sum must be at least equal to 500. Five even numbers are not enough (at most one of them can be equal to 100), while six are enough (it suffices to take the six largest even numbers). On the other hand, it is easy to construct a set $X$ with the required properties and with exactly 6 even numbers: it suffices to take, for example, all the odd numbers with the exception of the 6 numbers 1, 3, 5, 7, 9, 45 and all the even numbers 90, 92, 94, 96, 98, 100.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty, ordering) added by this project.