Set Theory

[BMAD]

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

[BMAD]

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.

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.