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

• Are you familiar with Ferrers diagrams? The Ferrers diagram for $n$ integers between $1$ and $k$ is the transpose of a Ferrers diagram for $k$ integers between $1$ and $n$. Perhpas one gets some mileage out of this observation. Feb 18, 2013 at 23:28
• You should probably make the distinction between set and multiset. As sets, $\{1,1,2,3,3\}$ and $\{1,2,3\}$ are equal. Repetitions are not counted for sets, whereas multisets do mind them (but not the order, of course). Feb 19, 2013 at 0:41
• @user62965: You misunderstand. Repetitions are allowed, as the OP's example makes clear. Feb 19, 2013 at 14:22
• After 18hrs without an answer, I'm beginning to feel not so bad about failing to crack this one .... Feb 19, 2013 at 17:18
• out of curiosity, how did you come across this ? Feb 19, 2013 at 17:28

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$$

• Great! I was beginning to suspect that it's too hard to solve... Feb 20, 2013 at 7:02

I've done this problem in my exam today. It's a nice problem and here is my solutuion: First, I denote $A=\{x_1,x_2,...,x_n\}$, $1\leq x_1\leq x_2\leq ...\leq x_n\leq k$ and $B=\{y_1,y_2,...,y_k\}$, $1\leq y_1\leq y_2\leq...\leq y_k\leq n$. Set $a_p=\sum_{i=1}^{p}x_i$ ($1\leq p\leq n$) and $b_q=\sum_{j=1}^{q} y_j$ ($1\leq q\leq k$).Without lost of general I can assume that $a_n\leq b_k$. From that, $\forall 1\leq p\leq n$, there exists $1\leq f(p)\leq k$ is the smallest index that $a_p\leq b_{f(p)}$. $$b_{f(1)}-a_1;...;b_{f(n)}-a_n$$ I comment that all $b_{f(i)}-a_i<n$ (if $n\leq b_{f(p)}-a_p$ with some $p$ $\rightarrow n<b_{f(p)}\rightarrow f(p)>1$, so we have $n\leq b_{f(p)-1}+y_{f(p)}-a_p\rightarrow 0\leq n-y_{f(p)}\leq b_{f(p)-1}-a_p\rightarrow a_p\leq b_{f(p)-1}$ (contradiction because I choose $f(p)$ is the smallest index))

If $b_{f(p)}-a_p=0$ with some $p$, I have the proof, if not, by the pingeonhole principle, we have $b_{f(r)}-a_r=b_{f(s)}-a_s$ with some $1\leq r< s\leq n$ $$\rightarrow b_{f(s)}-b_{f(r)}=a_s-a_r$$ $$\rightarrow \sum_{i=r+1}^{s}x_i=\sum_{j=f(r)+1}^{f(s)}y_j$$ So i have the proof. (do i have mistake in somewwhere?)

• Nice proof! I see no errors. Nov 27, 2019 at 16:13