Discrete Math problem Let S be a set of six positive integer

Discrete Math problem:

Let S be a set of six positive integers whose maximum is at most 14. Prove that the sums of the elements in all non-empty subsets of S cannot be distinct.

Please explain why you took each step. I\'m utterly confused by this problem.

Solution

There are 2^6-1=63 non-empty subsets and the sum of every subset of S is at most 9+10+...+14=69. So the pigeonhole pricincple cannot be applied directly. Instead, let\'s consider subsets of size at most 5. Their total sum is at most 10+11+..+14=60. There are 62 non-empty subsets with at most 5 elements. So at least two of them have equal sum.