wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Subsets of subsets with same sum
        
(Message started by: Aryabhatta on Sep 23^rd, 2008, 9:44pm)

Title: Subsets of subsets with same sum
Post by Aryabhatta on Sep 23^rd, 2008, 9:44pm

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.

Title: Re: Subsets of subsets with same sum
Post by pex on Sep 23^rd, 2008, 10:43pm

on 09/23/08 at 21:44:44, 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.

[hideb]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.[/hideb]

Interesting!

Title: Re: Subsets of subsets with same sum
Post by Hippo on Sep 24^th, 2008, 3:47am

This was fast ;) good job

Title: Re: Subsets of subsets with same sum
Post by Aryabhatta on Sep 24^th, 2008, 11:27am

Yes, well done!

Title: Re: Subsets of subsets with same sum
Post by cool_joh on Sep 26^th, 2008, 6:59pm

this is a problem from IMO 1972. it appeared on crux 1975 as well.