# 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$ Commented Mar 1, 2015 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. Commented Mar 1, 2015 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.

If the set does contain 1, the sum of the whole set has to be strictly less than 127. This is impossible, too, by the pigeonhole principle.

• 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$. Commented Mar 7, 2015 at 5:47
• @BrianM.Scott, isn't that the same as the condition I gave? I admit that there was a smalle mistake: 18 should not have been included in the list. Fortunately this mistake doesn't make any difference in the end. Commented Mar 7, 2015 at 14:23
• Yes, just stated a little more transparantly. Commented Mar 7, 2015 at 19:42
• @BrianM.Scott Nice explanation. A small typo: 112 should 122. Commented Sep 18, 2023 at 0:27

Obviously it is necessary that the 7 integers are distinct. Let $$x$$ be the minimum integer. Then the minimum sum of any (non-empty) subset is $$x$$ and the maximum value is $$x+19+20+21+22+23+24 = 129 + x.$$

Hence there are at most 130 different possible values for the sum of the 7 integers.

Suppose the number 24 was not part of our 7 integers, then the maximum sum would be $$x+18+19+20+21+22+23 = 123+x.$$

Then there would only be 124 different possible sums within our 2^7 -1 = 127 different subsets, contradicting uniqueness of each subset sum. So 24 must be one of our 7 numbers. An identical argument shows 23 and 22 must also members of our set of 7.

If we suppose 21 is not a member, we get a maximum sum of $$x + 18+19+20+22+23+24 = 126+x$$ which gives exactly 127 possible different sums for our 127 subsets. Thus for this to be possible, every number between $$x$$ and $$126+x$$ must be achieved as the sum of a subset of $$\{x,18,19,20,22,23,24\}$$. Since $$\{x+1\}$$ is such a number, we deduce $$x = 17$$. But then the sum $$21$$ can't be achieved (among many others).

Finally, we conclude that it must be the case that all of $$\{21,22,23,24\}$$ are among our 7 integers. But since $$21+24 = 22+23$$ we have another contradiction. Thus 127 distinct subsets are not possible.