Given 10 numbers a1, a2, . . . , a10, from the set S natural numbers S = {1, 2, 3, . . . , 100} . Prove that there exist two (or more) subsets of the 10 numbers whose elements sum to the same value.

Question

The answer needs to be in terms of the pigeonhole principle and it has to be a generalized answer.

Answer 1

Excluding the null set, which would be the unique subset that has the sum 0 anyway, there are 2^10 - 1 = 1023 subsets of a set of length 10.

A simple use of the pigeonhole principle which would work in this case would be to say that the smallest sum of a subset of length 10 of the integers from 1 to 100 is 1 - a set of length 1 containing the integer 1 - and the largest would be the maximum value of the set, which is 100 + 99 + 98 + . + 91 = 955

Now, to use the pigeonhole principle, as the set consists of only integers, and the sums range from 1 to 955, there is a maximum of 955 different values for the subsets. However, we have 1023 subsets, Thus, there must be matches.

Note that we can lessen the number of possible values. As we excluded the null set, exclude the set of length 10 (it, also, will be the unique set with this sum), and we have 2^10 - 2 subsets. While the minimum value remains 1, the maximum value is now 100 + 99 + ...+ 92 (there are only at most 9 members of the subset), so the maximum possible value is 864, so there are at most 864 possible values but there are 1022 subsets, so there must be matches.

A generalized answer might be that if we have a set {1, 2, ..., N} and subsets of length M,

we will have 2^M - 2 subsets of the subset not including the null set and the subset of length M, and the possible values range from 1 to N + N-1 + ... + N - M + 2 = NM - N - (M-1)(M-2)/2 = NM - N - 1/2M^2 +3/2M - 1 possible values.

If NM - N - 1/2M^2 +3/2M - 1 < 2^M - 2, we must have duplicates.

You could write

If NM - N - 1/2M^2 +3/2M + 1 - 2^M < 0, you have duplicates, but that doesn't show the essence of the pigeonhole principle as well.