Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

Set Theory


  • Please log in to reply
1 reply to this topic

#1 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1818 posts
  • Gender:Female

Posted 09 May 2013 - 09:44 PM

Let A be a list of n integers between 1 and k. Let B be a list of k integers between 1 and n. Prove that there's a non-empty subset of A and a (non-empty) subset of B having the same sum.

 

 

Example: Say n=3, k=5 and A={3,4,5}, B={1,1,2,3,3}. Then we can find {1,3,3} is contained in B and {3,4} contained in A with the same sum (I know there're are simpler solutions in this example, it's just for demonstration).

 


  • 0

#2 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1818 posts
  • Gender:Female

Posted 13 May 2013 - 09:35 PM

Spoiler for hint1

before you can prove anything you need to prove two lemmas

 

Spoiler for hint2

 

Spoiler for hint3

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users