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).

Posted

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).

## Share this post

## Link to post

## Share on other sites