# Pigeonhole question about distinct sums

How do I show with the pigeonhole principle that no seven positive integers not exceeding $24$ can have sums of all subsets different.

As observed by Ross Millikan, the simplest possible approach does not work. The maximum possible subset sum is $24+23+\cdots+18=147$, and the minimum possible subset sum is $0$. So as there are only $2^7=128$ subsets the pigeonhole principle does not force a collision. At least not without some sharpening.

• The simplest approach doesn't work. There are $2^7=128$ subsets. The maximum sum is $7 \cdot 21=147$ – Ross Millikan Mar 1 '15 at 17:41
• One can reduce the maximum sum a little (the collection can't contain 4 consecutive integers), but anything I can think still has max. sum greater than 128. – copper.hat Mar 1 '15 at 17:45

Suppose you had seven integers in $\{1,2,\dots,24\}$ so that all subsets have different sums. That means that there are $2^7=128$ different sums.
The set of seven integers cannot contain a quadruplet of the form $\{a,a+b,a+c,a+b+c\}$ (with all four numbers distinct) because otherwise it would contain two pairs with the same sum. Therefore the sum of the whole set cannot exceed $$24+23+22+20+18+13+7=127.$$ If the set does not contain the number 1, then the sums of different subsets are in the set $\{0,2,3,\dots,127\}$ which has strictly less than 128 elements, which is impossible.
• You can go further and show that the largest possible sum is at most $$24+23+22+20+17+12+4=112\;,$$ since the set cannot contain four distinct numbers of the form $a,a+d,b,b+d$. – Brian M. Scott Mar 7 '15 at 5:47