2
$\begingroup$

For a positive integer $n$ and two integer sequences $a_1,a_2...a_n$ and $b_1,b_2...b_n$ where $\forall i$, $a_i,b_i \in [1,n]$, I want to find two non-empty subsets, one in each sequence, with the same sum.

i.e. I want to find $1 \leq i_1<i_2 <\cdots <i_p \leq n$ and $1 \leq j_1<j_2 <\cdots < j_q \leq n$ where $p,q \geq 1$ and $\sum_{x=1}^p a_{i_x}=\sum_{y=1}^q b_{j_y}$.

From trying small cases, I highly suspect that such subsets exist for any $a$ and $b$, but I can't find a rigorous proof for that.

$\endgroup$
2
$\begingroup$

This solution is paraphrased from Mathematical Mind-Benders by Peter Winkler, a math puzzle anthology where this puzzle appears.


For each $k\ge 0$, let $$ s_k=a_1+a_2+\dots+a_k,\\ t_k=b_1+b_2+\dots+b_k, $$ with the convention that $s_0=t_0=0$. Assume WLOG that $s_n\le t_n$, which can achieved by possibly switching $a$ and $b$. Further assume $s_n<t_n$, since in case $s_n=t_n$ the entire sets work.

For each $k=0,1,\dots,n$, let $k'$ be the largest element of $\{0,1,\dots,n-1\}$ for which $s_{k}\ge t_{k'}$. Note that $k'$ exists; there is at least one index $k'$ for which $s_k\ge t_{k'}$, since $s_k\ge t_0$.

We then have that $$ 0\le s_k-t_{k'}\le n-1. $$ The left inequality is obvious. The right inequality follows by the maximality of $k'$; if $s_k\ge t_{k'}+n$, then you would also have $s_k\ge t_{k'+1}$.

Since $k$ can take any of $n+1$ values between $0$ and $n$ inclusive, but $s_{k}-t_{k'}$ can only take $n$ values between $0$ and $n-1$ inclusive, by the pigeonhole principle, there must exist indices $k\ge h$ for which $$ s_k-t_{k'}=s_h-t_{h'}, $$ which implies $$ s_k-s_h=a_{h+1}+\dots+a_k=b_{h'+1}+\dots+b_{k'}=t_{k'}-t_{h'}, $$ so we have found our two equal subsets.

$\endgroup$

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.