Question

Let us choose seven arbitrary distinct positive integers, not exceeding 24. Show that there will be at least two subsets chosen from these seven numbers with equal total sums. (Keep in mind that sets, and hence subsets, have no repeated elements.) Hint: How many subsets can you form altogether? What is the largest total sum of such a subset?

Answer 1

There are 7 distinct integers. The power set (i.e set of all possible subsets) has cardinality 2^n, for a set of size n. Thus, with 7 integers (removing the empty set), we can form 2^7-1 possible subset combinations. Thus there are 127 subsets. The maximum sum can be obtained if we choose the largest 7 numbers. Thus the largest possible sum is: 24+23+22+21+20+19+18=147.

However, now note that if we can form this sum as a total sum of a subset, then it must be the case that we have chosen these particular numbers: 18,...,24. Thus, we can't form the sum 1. Similarly if we can have a subsets summing to 1, then it must be the singleton 1 and hence e cannot form the sum 147 as total of a subset.

Thus, the subsets can't take at least one out of the following sums: 1,...,147. Hence, there are at most 146 possible sums and 147 distinct subsets. By pegion hole principle, at least two subsets must have the same sum.