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

Question

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$?

Answer 1

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 pigeonholes)? How many nonempty subsets of up to $9$ elements are there (your pigeons)?

Answer 2

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 ... ?

Answer 3

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).