let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subests of A cannot all be distinct

Question

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subsets of A cannot all be distinct.

for when does this not continue to hold up ( ie instead of 12 , its 13,....)

Answer 1

There are $2^6=64$ possible subsets of $A$, the sums of all of them is less than $12+11+10+9+8+7=57$. There is not enough room for the sums to be all distinct.

Answer 2

As $|A| = 6$, $|\mathcal P(A)| = 2^6 = 64$, so there are at most 64 distinct sums.

Now, note that $12 + 11 + 10 + 9 + 8 + 7 = 57$, and so no subset of $A$ can sum to more than $57$, by distinctness of the elements of $A$. Further, as each element of $A$ is positive, no subset of $A$ can sum to less than $0$.

Therefore, the possible sums for subsets of $A$ are the integers between $0$ and $57$, inclusive. There are precisely 58 of these, and as $58 < 64$, by the pigeonhole principle, some sum must be reached by at least two subsets.

(If we instead consider numbers $\le 13$, then this argument breaks down. $13 + 12 + 11 + 10 + 9 + 8 = 63$, which gives that there are exactly 64 possible sums.)

Answer 3

put $n$ instead of 12.

the sum of the integers is bounded by $6n-15$, whilst there are $2^6-1$ non-empty subsets