Here’s a riddle that I’ve been struggling with for a while:
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}⊂B and {3,4}⊂A with the same sum (I know there’re are simpler solutions in this example, it’s just for demonstration).
I tried to attack it from different directions: induction, pigeon-hole, combinatorics, but I couldn’t make it work. Suggestions?
Addition
As this was so highly voted, I thought I should tell how I came about this riddle – it’s an interesting story: I heard it from a friend of mine about 10 years ago when I just finished high school and he just graduated in math. I remeber him telling me the riddle and his solution, and I thought “math is so cool, some day I’ll also have a degree in math and will be able to solve riddles like this”. I don’t know why I suddenly remembered this conversation, and why I remember only the problem and not the solution. but it turns out that now I have a degree, but I still can’t.
Answer
Nice problem! I almost hate to post a solution. If you like puzzles and haven’t put in any time on this one yet, I encourage you not to read further.
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 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.
Example: Taking A=(3,4,5) and B=(1,1,2,3,3) as in the OP, we have
sA deckB deckA cards usedB cards used034511233345112333245123311452331−14533235334053353523
At this point we stop, because the next step would be to draw from the B deck, but the B deck is empty. (In this example, the A deck is also empty, but that is a coincidence; they don’t have to both run out.)
Lemma 1: The numbers sj are always between −n+1 and k.
Proof by induction on j. The base case is true. If sj is between −n+1 and 0, then sj+1 is between −n+k+1 and k; if sj is between 1 and k then sj+1 is between −n+1 and −n+k. Since the intervals [−n+1,0] and [1,k] cover every integer in [−n+1,k], this shows that, if sj∈[−n+1,k] then sj+1∈[−n+1,k]. ◻.
Lemma 2: The sequence sj repeats a value. (In the example, the values 0, 2 and 3 are repeated.)
Let’s suppose that the game ends when we try to draw from the B stack; the other case is similar. So we must make k+1 attempts to draw from the B-stack (including the attempt that fails). At the time that we make each attempt, sj is positive. So we have k+1 positive values of sj. By Lemma 1, each of these values lies in [1,k]. So some value must appear more than once. ◻
Proof of the result Let si=sj. Then the set of A cards which are dealt between si and sj must have the same value as the set of B cards. For example, if we use the repeated 3‘s in the example sequence, then we see that −1−1−2+4=0 or, in other words, 4=1+1+2. ◻
Attribution
Source : Link , Question Author : yohBS , Answer Author : user1001001