wu :: forums - Print Page


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

        riddles >> medium >> Multiple Subset Sum
        
(Message started by: Vote4Nixon on Jul 19^th, 2011, 12:12am)

Title: Multiple Subset Sum
Post by Vote4Nixon on Jul 19^th, 2011, 12:12am

You are given two sets: X containing 19 positive integers each less than or equal to 93 and Y containing 93 positive integers each less than or equal to 19.

Prove that there exists a non-empty subset of X that sums to the sum of a subset of Y.

Title: Re: Multiple Subset Sum
Post by Michael Dagg on Jul 25^th, 2011, 8:53am

Hint: [hide]See Dirichlet's box principle. To get the objects, consider a
third set Z of order 19 whose elements are the difference between a
certain sum of elements of Y and an increasing sum of the elements of X.
The elements of Z are your boxes.
[/hide]