• 0

Set Theory

Question

Posted · Report post

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

Share this post


Link to post
Share on other sites

1 answer to this question

  • 0

Posted · Report post

Imagine writing the numbers in A on a stack of cards, one number per card. We write the numbers of B on a separate stack, again one per card. We then can recursively define a sequence sj as follows:

Initial value: s0=0

If sj ≤ 0, look at the top card of the A stack, let the number written on it be a. Set sj+1 = sj + a, and remove that card from the stack

if sj > 0, look at the top card of the B stack; let the number written on it be b. Set sj+1 = sj - b, and remove that card from the stack. Continue until you attempt to draw a card from an empty stack.

post-53485-0-49161100-1368477354_thumb.p

before you can prove anything you need to prove two lemmas

L1-->the numbers sj are always between -n+1 and k.

L2-->The sequence sj repeats a value.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.