wu :: forums - Subsets of subsets with same sum

wu :: forums « wu :: forums - Subsets of subsets with same sum » Welcome, Guest. Please Login or Register. Nov 25^th, 2024, 1:42am
RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

   wu :: forums
   riddles
   medium (Moderators: Icarus, Grimbal, Eigenray, SMQ, william wu, ThudnBlunder, towr)
   Subsets of subsets with same sum

« Previous topic | Next topic »

Pages: 1

Notify of replies

Send Topic

Author

Topic: Subsets of subsets with same sum (Read 3670 times)

Aryabhatta
Uberpuzzler

Gender:

Posts: 1321

Subsets of subsets with same sum
« on: Sep 23^rd, 2008, 9:44pm »

Quote

Modify

A puzzle from a book by Peter Winkler.

Prove that every set of ten distinct integers between 1 and 100 (inclusive), contains two disjoint non-empty subsets with the same sum.

IP Logged

pex
Uberpuzzler

Gender:

Posts: 880

Re: Subsets of subsets with same sum
« Reply #1 on: Sep 23^rd, 2008, 10:43pm »

Quote

Modify

on Sep 23^rd, 2008, 9:44pm, Aryabhatta wrote:

Prove that every set of ten distinct integers between 1 and 100 (inclusive), contains two disjoint non-empty subsets with the same sum.

hidden:

Let S be a set of ten distinct integers from 1-100. S has 2¹⁰ subsets; not counting the empty subset, we are left with 2¹⁰ - 1 = 1023 nonempty subsets.

Any such subset has sum at least 1 and at most 91 + 92 + ... + 100 = 955. Obviously, the sums have to be integer. Thus, there can be no more than 955 different subset sums.

By the pidgeonhole principle, there must be two out of the 1023 subsets of S that have the same sum; call them A and B. If A and B are disjoint, we're done. Otherwise, we can remove their intersection from both subsets. As A and B are by construction different subsets with the same sum, the resulting subsets after this removal are still both nonempty. Now, they are also disjoint, and we're also done in this case.

Interesting!

IP Logged