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.

  • 1
    $\begingroup$ The simplest approach doesn't work. There are $2^7=128$ subsets. The maximum sum is $7 \cdot 21=147$ $\endgroup$ – Ross Millikan Mar 1 '15 at 17:41
  • $\begingroup$ 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. $\endgroup$ – 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.

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

  • $\begingroup$ 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$. $\endgroup$ – Brian M. Scott Mar 7 '15 at 5:47
  • $\begingroup$ @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. $\endgroup$ – Joonas Ilmavirta Mar 7 '15 at 14:23
  • $\begingroup$ Yes, just stated a little more transparantly. $\endgroup$ – Brian M. Scott Mar 7 '15 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.