# A discrete math riddle

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?

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.

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 $$AA$$ on a stack of cards, one number per card. We write the numbers of $$BB$$ on a separate stack, again one per card. We then recursively define a sequence $$sjs_j$$ as follows:

Initial value: $$s0=0s_0=0$$.

If $$sj≤0s_j \leq 0$$, look at the top card of the $$AA$$ stack; let the number written on it be $$aa$$. Set $$sj+1=sj+as_{j+1} = s_j+a$$, and remove that card from the stack.

If $$sj>0s_j > 0$$, look at the top card of the $$BB$$ stack; let the number written on it be $$bb$$. Set $$sj+1=sj−bs_{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)A = ( 3,4,5 )$$ and $$B=(1,1,2,3,3)B = (1,1,2,3,3)$$ as in the OP, we have
$$sA deckB deckA cards usedB cards used034511233345112333245123311452331−14533235334053353523\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 $$BB$$ deck, but the $$BB$$ deck is empty. (In this example, the $$AA$$ deck is also empty, but that is a coincidence; they don’t have to both run out.)

Lemma 1: The numbers $$sjs_j$$ are always between $$−n+1-n+1$$ and $$kk$$.

Proof by induction on $$jj$$. The base case is true. If $$sjs_j$$ is between $$−n+1-n+1$$ and $$00$$, then $$sj+1s_{j+1}$$ is between $$−n+k+1-n+k+1$$ and $$kk$$; if $$sjs_j$$ is between $$11$$ and $$kk$$ then $$sj+1s_{j+1}$$ is between $$−n+1-n+1$$ and $$−n+k-n+k$$. Since the intervals $$[−n+1,0][-n+1, 0]$$ and $$[1,k][1, k]$$ cover every integer in $$[−n+1,k][-n+1, k]$$, this shows that, if $$sj∈[−n+1,k]s_j \in [-n+1, k]$$ then $$sj+1∈[−n+1,k]s_{j+1} \in [-n+1,k]$$. $$◻\square$$.

Lemma 2: The sequence $$sjs_j$$ repeats a value. (In the example, the values $$00$$, $$22$$ and $$33$$ are repeated.)

Let’s suppose that the game ends when we try to draw from the $$BB$$ stack; the other case is similar. So we must make $$k+1k+1$$ attempts to draw from the $$BB$$-stack (including the attempt that fails). At the time that we make each attempt, $$sjs_j$$ is positive. So we have $$k+1k+1$$ positive values of $$sjs_j$$. By Lemma 1, each of these values lies in $$[1,k][1,k]$$. So some value must appear more than once. $$◻\square$$

Proof of the result Let $$si=sjs_i=s_j$$. Then the set of $$AA$$ cards which are dealt between $$sis_i$$ and $$sjs_j$$ must have the same value as the set of $$BB$$ cards. For example, if we use the repeated $$33$$‘s in the example sequence, then we see that $$−1−1−2+4=0-1-1-2+4=0$$ or, in other words, $$4=1+1+24=1+1+2$$. $$◻\square$$