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$?
Best Answer
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)?