Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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. –  Gerry Myerson Feb 18 '13 at 23:28
4  
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). –  Asaf Karagila Feb 19 '13 at 0:41
6  
@user62965: You misunderstand. Repetitions are allowed, as the OP's example makes clear. –  Peter Smith Feb 19 '13 at 14:22
2  
After 18hrs without an answer, I'm beginning to feel not so bad about failing to crack this one .... –  Peter Smith Feb 19 '13 at 17:18
5  
out of curiosity, how did you come across this ? –  Glougloubarbaki Feb 19 '13 at 17:28
show 3 more comments

1 Answer 1

up vote 17 down vote accepted

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_{k+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$

share|improve this answer
    
Great! I was beginning to suspect that it's too hard to solve... –  yohBS Feb 20 '13 at 7:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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