Set question?

Question

Let set A be a 90-element subset of {1,2,3,...,100}, and let S be the sum of the elements of A. Find the number of possible values of S.

I know the answer is 901, but I don't know how to get the answer except through the long way of adding elements together and checking.

Answer 1

One approach is to find the smallest and largest possible sums. You'll be able to get any sum in between.

Smallest: 1+ 2 + ... + 90 = 90(91)/2 = 4095.
Largest: 11 + 12 + ... + 100 = 90(111)/2 = 4995.

Number of different possible sums = 4995 - 4095 + 1 = 901.


To illustrate why you can get every sum between smallest and largest, consider a smaller problem in which you keep only two numbers from the list 1, 2, 3, 4, 5. Unless you've got the numbers 4 and 5, there will be a "missing" number that is bigger than--and adjacent to--some number you have. For instance, if you have 2 and 5, you are missing 3. By exchanging your 2 for the 3, you increase your sum by 1. You can continue this process of exchanges until you reach the maximum sum, hitting every whole number on the way.

Answer 2

To formalize the proof that you get every integer in the interval between the obvious min and the obvious max, use induction.

The key point is that either there is some k in S such that k+1 is not in S, or else S is exactly the set of integers 11, 12, 13, .... , 100