# Show that for any subset of $10$ distinct integers there exists two disjoint subsets equal in sum

The title abbreviates the following homework exercise on the Pigeonhole Principle.

Show that for any set of $10$ distinct integers from $1 \dots 60$ there exists two disjoint subsets of equal sum. (The $2$ disjoint sets may not include all $10$ integers. e.g. let a set of $10$ distinct integers contain $\{1,2,3\}$. Subsets $\{1,2\}, \{3 \}$ are disjoint and have equal sums.)

Can anyone give a hint at how or why this problem is an application of the Pigeonhole Principle? Second, does the result to be proved hold for sets of integers $\{1 \dots n \}$ where $n \ne 60$?

• For the last question no. Doesn't hold for $n=2$ – Guy Mar 12 '14 at 9:38
• @Sabyasachi: Yes it does, vacuously. Because there is no set of 10 distinct integers from 1...2, anything at all can be said to hold for all such sets. – TonyK Mar 12 '14 at 9:56
• @TonyK oh. I thought at most 10 elements. Not exactly 10. – Guy Mar 12 '14 at 9:57
• So at least, this is true for all $n \le 60$. – Du Phan Mar 12 '14 at 9:58
• By the answer of @vonbrand, this is true for $n \le 117$. With $n=117$, there are 1017 values of sums, and 1022 subsets (exclude the empty, and the whole subsets). – Du Phan Mar 12 '14 at 10:06

## 3 Answers

Given any set of 10 numbers up to 60, how many different sums are possible for nonempty subsets of at most 9 of them (your pigenholes)? How many pairs of disjoint nonempty subsets of 10 elements are there (your pigeons)?

• Brilliant! An additional hint is that from two different (not disjoint) subsets with the same sum, one can construct two disjoint subsets with the same sum. – Du Phan Mar 12 '14 at 9:56
• "How many pairs of disjoint nonempty subsets...": Shouldn't that be "How many nonempty subsets with up to nine elements..."? – TonyK Mar 12 '14 at 10:01

Take such a set. You can select the first subset in $2^{10}-2=1022$ ways. The sum of the elements in $A$ is between $1$ and $52+53+\cdots+60=504$, so there are two distinct subsets $A_i$ and $A_j$ with the same sum. Let $B=A_i \cap A_j$, $A'_i=A_i-B$, $A'_j=A_j-B$. Since $A_i\neq A_j$, $A'_i$ and $A'_j$ are disjoint, not empty and have the same sum.

This result holds for other numbers greater than $60$, but not much greater. Let $k$ be that number. In order to apply the pigeonhole principle, the sum $k+(k-1)+\cdots+(k-8)=8k-36$ must not be greater than $1021$. The inequality $$8k-36\leq1021$$ holds for $k\leq 132$. I'm not saying, of course, that the statement doesn't hold for $k=133$ (I don't know if it holds or not).

• The statement does not hold for $k=337$ as shown by the example which I gave in my comment on the question. – bof Mar 12 '14 at 17:00

HINT to OP part 2: Note that $1, 2, 4$ is a set of three numbers for which every subset has a different sum. Can you see how to extend this to four numbers ... ?

• Extend it to four numbers? Let's see . . . $\{3,5,6,7\}$. Did I get it right? :-) – bof Mar 12 '14 at 10:42
• @bof: I think what Mark had in mind was $\{1,2,4,8\}$ (but your guess has merits too). – TonyK Mar 12 '14 at 20:51
• @TonyK My suggestion was to find a simple way of showing there was a limit. bof's suggestion has a lower top value, which is not so easy to see, but indicates there is more to finding the exact limit. – Mark Bennet Mar 12 '14 at 20:59