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\}\subset B$ and $\{3,4\}\subset 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.
Best 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 $s_j$ as follows:
Initial value: $s_0=0$.
If $s_j \leq 0$, look at the top card of the $A$ stack; let the number written on it be $a$. Set $s_{j+1} = s_j+a$, and remove that card from the stack.
If $s_j > 0$, look at the top card of the $B$ stack; let the number written on it be $b$. Set $s_{j+1} = s_j-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 $$\begin{array}{|rrrrr|} \hline s & A \ \mbox{deck} & B \ \mbox{deck} & A \ \mbox{cards used} & B \ \mbox{cards used} \\ \hline 0 & 345 & 11233 & & \\ \hline 3 & 45 & 11233 & 3 & \\ \hline 2 & 45 & 1233 & & 1 \\ \hline 1 & 45 & 233 & & 1 \\ \hline -1 & 45 & 33 & & 2 \\ \hline 3 & 5 & 33 & 4 & \\ \hline 0 & 5 & 3 & & 3 \\ \hline 5 & & 3 & 5 & \\ \hline 2 & & & & 3 \\ \hline \end{array}$$
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 $s_j$ are always between $-n+1$ and $k$.
Proof by induction on $j$. The base case is true. If $s_j$ is between $-n+1$ and $0$, then $s_{j+1}$ is between $-n+k+1$ and $k$; if $s_j$ is between $1$ and $k$ then $s_{j+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 $s_j \in [-n+1, k]$ then $s_{j+1} \in [-n+1,k]$. $\square$.
Lemma 2: The sequence $s_j$ 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, $s_j$ is positive. So we have $k+1$ positive values of $s_j$. By Lemma 1, each of these values lies in $[1,k]$. So some value must appear more than once. $\square$
Proof of the result Let $s_i=s_j$. Then the set of $A$ cards which are dealt between $s_i$ and $s_j$ 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$. $\square$