wu :: forums « wu :: forums - Multiple Subset Sum » Welcome, Guest. Please Login or Register. Nov 28th, 2024, 6:50am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    medium (Moderators: Grimbal, Icarus, SMQ, towr, ThudnBlunder, william wu, Eigenray)    Multiple Subset Sum « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Multiple Subset Sum  (Read 1478 times) Vote4Nixon Newbie     Posts: 1 Multiple Subset Sum   « on: Jul 19th, 2011, 12:12am » Quote Modify 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. IP Logged Michael Dagg Senior Riddler     Gender: Posts: 500 Re: Multiple Subset Sum   « Reply #1 on: Jul 25th, 2011, 8:53am » Quote Modify Hint:  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. IP Logged Regards, Michael Dagg Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board