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.

  • 2
    $\begingroup$ 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. $\endgroup$ Feb 18, 2013 at 23:28
  • 5
    $\begingroup$ 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). $\endgroup$
    – Asaf Karagila
    Feb 19, 2013 at 0:41
  • 6
    $\begingroup$ @user62965: You misunderstand. Repetitions are allowed, as the OP's example makes clear. $\endgroup$ Feb 19, 2013 at 14:22
  • 2
    $\begingroup$ After 18hrs without an answer, I'm beginning to feel not so bad about failing to crack this one .... $\endgroup$ Feb 19, 2013 at 17:18
  • 5
    $\begingroup$ out of curiosity, how did you come across this ? $\endgroup$
    – Albert
    Feb 19, 2013 at 17:28

2 Answers 2


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$

  • $\begingroup$ Great! I was beginning to suspect that it's too hard to solve... $\endgroup$
    – yohBS
    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?)

  • 1
    $\begingroup$ Nice proof! I see no errors. $\endgroup$ Nov 27, 2019 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.