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.
The difference between the sum of your five numbers and the smallest of your five numbers plus $1$ gives you the size of the range your sums can land in. This can be at most $31$, which is only attained if your numbers include $6,7,8,9$.
To see this note that size of range of $9,8,7,6,5$ is $35-5+1=31$, and lowering the bottom number does not effect this, but lowering any other number does lower it.
Thus the five numbers must include $6,7,8,9$, as if the range has size less than $31$, then the $31$ sums cannot be distinct. However $6+9=7+8$ so the sums are not distinct.