wu :: forums « wu :: forums - Matching sets » Welcome, Guest. Please Login or Register. May 19th, 2024, 11:49am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    medium (Moderators: Eigenray, Grimbal, towr, SMQ, ThudnBlunder, Icarus, william wu)    Matching sets « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Matching sets  (Read 644 times) amichail Senior Riddler     Posts: 450 Matching sets   « on: Dec 26th, 2006, 8:34pm » Quote Modify Consider two multisets of numbers S and T, each containing n integer numbers in the range 1..n (since they are multisets, repeating the same number several times is allowed). Prove, that there are two subsets A and B, of S and T, respectively, such that the total sum of the numbers in A is equal to the total sum of numbers in B.   http://valis.cs.uiuc.edu/blog/index.php/archives/2006/12/24/matching-set s/ IP Logged DropZap - a new kind of block elimination game Aryabhatta Uberpuzzler     Gender: Posts: 1321 Re: Matching sets   « Reply #1 on: Jan 14th, 2007, 11:33am » Quote Modify No one has tried this? IP Logged amichail Senior Riddler     Posts: 450 Re: Matching sets   « Reply #2 on: Jan 14th, 2007, 11:35am » Quote Modify I tried and failed   IP Logged DropZap - a new kind of block elimination game Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Matching sets   « Reply #3 on: Jan 15th, 2007, 3:49am » Quote Modify I assume A and B can not be empty?   IP Logged amichail Senior Riddler     Posts: 450 Re: Matching sets   « Reply #4 on: Jan 15th, 2007, 6:01am » Quote Modify on Jan 15th, 2007, 3:49am, Grimbal wrote: I assume A and B can not be empty?   Yes, they are not empty. IP Logged DropZap - a new kind of block elimination game SMQ wu::riddles Moderator Uberpuzzler     Gender: Posts: 2084 Re: Matching sets   « Reply #5 on: Jan 15th, 2007, 7:34am » Quote Modify Well, let's start with the obvious:   1. If the intersection of S and T is non-empty then A = B = S intersect T is a solution.   2. Correlary to 1: If either S or T = {1, 2, ..., n } then the intersection of S and T is non-empty   3. Correlary to 1: If S and T are disjoint then only one of S or T can contain the value n.   4. If S and T are disjoint and neither contains the value n, then there exist subsets of both S and T containing n-1 elements of values 1 through n-1.   5. Likewise if S and T are disjoint and whichever contains the value n contains only one element of value n, then there exist subsets of both S and T containing n-1 elements of values 1 through n-1.   So the only cases requiring nore in-depth analysis are those where S and T are disjoint and either S or T contains multiple elements of value n.   --SMQ IP Logged --SMQ 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