4

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

NaN
  • 1,417
  • For the last question no. Doesn't hold for $n=2$ – Guy Mar 12 '14 at 09: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 09:56
  • @TonyK oh. I thought at most 10 elements. Not exactly 10. – Guy Mar 12 '14 at 09:57
  • So at least, this is true for all $n \le 60$. – Du Phan Mar 12 '14 at 09: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
  • 1
    It's false for $n\ge337$ because the ten numbers $165,249,291,313,324,330,333,335,336,337$ have $1024$ different sums, counting the empty sum and the whole works. – bof Mar 12 '14 at 10:36

3 Answers3

6

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

vonbrand
  • 27,812
  • 1
    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 09:56
  • 3
    "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
  • @TonyK, fixed. Thanks! – vonbrand Mar 24 '21 at 16:23
4

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

ajotatxe
  • 65,084
  • 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
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 ... ?

Mark Bennet
  • 100,194
  • Extend it to four numbers? Let's see . . . ${3,5,6,7}$. Did I get it right? :-) – bof Mar 12 '14 at 10:42
  • 1
    @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