2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ For the last question no. Doesn't hold for $n=2$ $\endgroup$ – Guy Mar 12 '14 at 9:38
  • $\begingroup$ @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. $\endgroup$ – TonyK Mar 12 '14 at 9:56
  • $\begingroup$ @TonyK oh. I thought at most 10 elements. Not exactly 10. $\endgroup$ – Guy Mar 12 '14 at 9:57
  • $\begingroup$ So at least, this is true for all $n \le 60$. $\endgroup$ – Du Phan Mar 12 '14 at 9:58
  • $\begingroup$ 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). $\endgroup$ – Du Phan Mar 12 '14 at 10:06
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Du Phan Mar 12 '14 at 9:56
  • 2
    $\begingroup$ "How many pairs of disjoint nonempty subsets...": Shouldn't that be "How many nonempty subsets with up to nine elements..."? $\endgroup$ – TonyK Mar 12 '14 at 10:01
3
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ Extend it to four numbers? Let's see . . . $\{3,5,6,7\}$. Did I get it right? :-) $\endgroup$ – bof Mar 12 '14 at 10:42
  • $\begingroup$ @bof: I think what Mark had in mind was $\{1,2,4,8\}$ (but your guess has merits too). $\endgroup$ – TonyK Mar 12 '14 at 20:51
  • $\begingroup$ @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. $\endgroup$ – Mark Bennet Mar 12 '14 at 20:59

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.