Let s be a set of five positive integers at most 9. Prove that the sums of the elements in all the non empty subsets of s cannot be distinct.? Let s be the set of five positive integer the maximum of which is at most 9 prove that the sums of the elements in all the non empty subset of as cannot be distinct?
Note:
I know this is similar to another question with 6 elements with max 14.
I saw this in Quora, and it annoys me that my proof is essentially
a backtracking proof to eliminate all the possibilities.
It starts like this:
They have to be distinct or else two 1-element sets have the same sum.
If the largest is 8 then the largest the set can be is 8-7-6-5-4 which sums to 30 but there are 31 possible sets so this can not be.
So 9 is there.
If 8 is there then 1 can’t be.
And so on.
My questions:
(1) If there a more elegant proof?
(2) What is the proper generalization replacing 9 and 5?
They all must be distinct,
so if the max is $n$
and there are $m$ of them
then to force the max to be $n$
we must have
$(n-1)+(n-2)+...(n-m)
\lt 2^m-1
$
or
$mn-\dfrac{m(m+1)}{2}
\lt 2^m-1
$
or
$n
\lt \dfrac{2^m-1}{m}+\dfrac{m+1}{2}
$.
For $m=5$ this is
$n \lt \dfrac{31}{5}+3
=9+\dfrac15
$
so
$n \le 9$.
But I don't see how to
elegantly prove
nonexistence.

Hint: Pigeonhole principle.  You can form $31$ sums in total from the non-empty subsets of the five numbers.  What is the largest such possible sum? What is the smallest?
